Sorry for bringing this back up but I have a similar issue.
It's especially annoying since I even re-bought AOEIII (even though I already had it) after I lost it when moving house.
I recently got a new computer too, with Windows 7 and I'm getting the
"the color scheme has been changed to Windows 7 Basic..." message... then nothing, the game doesn't even start :(
I tried right clicking the AOE3 shortcut, selecting 'properies' but there is no compatibility tab??