It seems like a problem with ATI graphics card, the latest drivers cannot handle AoC. Fortunately, there is a very simple solution to this: Go to "Start -> Run -> type "dxdiag" and click Ok. A new window will pop up -> go to Display and in the middle you can see DirectX settings -> disable DirectDraw Acceleration. Done
When you want to play some other games, you need to enable it again but it's not a problem as it can be done in the matter of a few seconds.