heh, LOTS of people have had LOTS of problems with gamespy.
Make sure you use the link to play over the net from within the game, NOT login to gamespy etc. As for the CD key, I've had that problem myself lots and lots of times.
I know it's plain silly, but that's the way things are.