With the widespread adoption of electronic government services, there has been a need to ensure a seamless flow of information across public sector organizations, while at the same time, maintaining confidentiality, integrity and availability. Governments have put in place various initiatives and programs including information security awareness to provide the needed understanding on how public sector employees can maintain security and privacy. Nonetheless, the implementation of such initiatives often faces a number of challenges that impede further take-up of e-government services. This paper aims to provide a better understanding of the challenges contributing towards the success of information security awareness initiatives implementation in the context of e-government. Political, organizational, social as well as technological challenges have been utilized in a conceptual framework to signify such challenges in e-government projects. An empirical case study conducted in a public sector organization in Greece was exploited in this research to reflect on these challenges. While, the results from this empirical study confirm the role of the identified challenges for the implementation of security awareness programs in e-government, it has been noticed that awareness programmers often pursue different targets of preserving security and privacy, which sometimes results in adding more complexity to the organization.