Well the fact that you can eventually "get in" (im not too familiar with the game) suggests your CD key is fine, so i would say this has to do with any firewalls perhaps preventing the authentication process, or just dodgy old auth servers.
A quick Google reveals its a 6 year old game and connection to the Ensemble Studios Online ( ESO) server is required for online play. Double check your firewall for that.

Remember when buying these old games that require online authentication - it costs money to run an auth server, and if the purchase involves only a one off fee there is very little incentive to keep an auth server running efficiently after a few years

Yea its not your Firewall mate.

Found this:

"Attention: Anyone who cannot log on. You purchased the game a bit late; MS has sold rights to the game to: Ubisoft, Xplosiv, and Valusoft. They have issued the same CD keys for all their products, meaning you have to share your CD key with 100+ or so other people(The last 10 digits are random, but the first 15 aren't. This reduces the number of possible CD keys by quite a lot). To receive a new CD key, email your vendor(Look on your box, and all over for who your vendor is) asking for a new CD key. They may require proof of purchase, which means you may have to mail your receipt, your CD key(Whatever it's on, the whole thing), or whatever is specified. You may also want to check this thread: http://aom.heavengames.com/cgi-bin [...] 5980,0,365 "

Its apparantly a very widespread problem. Try registering your product key with the distributor, chances are this has already been done by someone else though.
Other than that....you need to get yourself a unique key issued and you need to make sure it stays unique to you by registering yourself!