The implementation of e-government is a challenging task in any developed political context, but all the more uniquely so in the post-communist transitioning countries. These countries are struggling with the transformation of their legacy bureaucratic and administrative processes. In spite of the considerable literature on e-government, we still do not have a comprehensive, holistic framework in place that assesses the potential of e-government by taking into consideration all the critical dimensions. The complexity of government-to-constituent interactions needs to be analyzed comprehensively. In this paper, we analyze e-government interactions from two different perspectives. First, we de-construct the critical dimensions of a typical e-government interaction. Next, we conduct a step-by-step task decomposition to make realistic recommendations for opportunity areas that can be optimized through the inclusion of automated solutions. We aim to develop a framework for the evaluation of e-governance potential of transitioning countries and analyze the challenges from several perspectives.