I know very well the frustrations of trying to find a fix for this. I tried everything, but the one thing that worked for me 100% was to switch to the Windows Classic Theme and open the Screen Resolution window. However, I don't like using the Windows Classic theme because I, personally think, that it is very ugly (come on, if I'm gonna use Windows 7, I want it to look pretty

), and I don't personally like to have to open the Screen Resolution window every time I want to play.
So I've spent the last 6 hours or so doing much research and have created a batch file that automatically switches my Windows theme to Classic, open up the Screen resolution window, and run Age of Empires. After exiting my game, the batch file then reverts my Windows theme back to what it originally was and closes out the Screen resolution window.
With this taking so much time, I decided that I did not want to keep this to myself, and I have taken the time to upload the files I created so I could share with everybody that has this problem.
Here is the download link:
Windows 7 Conquerors Color Fix.zip
Instructions on how to use these files are included in the readme file (very, very highly recommended that you read it before doing anything with the files.)
I hope this helps somebody, I know it helps me immensely!