Need a new product key for Age of Mythology & the Titans Expansion

I purchased Age of Mythology for the sole purpose of playing a friend online.
I installed game with the product key that was provided. (The game was
purchased at Staples and is a Microsoft version.) I try to get online and it
says that it can not validate my cd key and I need to wait a few minutes. I
did some research on this and was told that my cd key was probably one that
was mass produced, and that I should try to buy another copy. Which I did.
I bought a Age of Mythology with the Titans Expansion from Gamestop, also a
Microsoft version. I uninstalled the first version that I had and proceeded
to install the new version of Age of Mythology and then installed the Titans
Expansion. I still get the same message as before when I try to play online.
CD cannot be validated please wait a few minutes. Please email me a new
product key so that I can play this game as I intended to when I bought it.
I have spent money on 2 copies and am getting frustrated that I cannot play
online, which was the only reason I bought the game.

I recently looked at the product keys on both of the Age of Mythology
booklets...and they are the SAME.