This is an issue with the "GENIE" Engine that AOE2 uses as well as AOE1. The games use 256 Colour palettes, but are unable to fully realize all the colours in the palette because Windows Explorer refuses to let it change some of the colours in the palette.
You can fix the colour issue if you terminate Explorer.exe before you run Age of Empires 1 or 2.