Activation Not Working (AppleID problem)

So I finally got my iPhone and I'm trying to activate it. That AT&T part went fine now I'm trying to log in using my apple ID and password, it says "There was an error trying to authenticate your iTunes Store account." I've got the right password and stuff; I even reset my password and tried that. Furthermore, as a test I tried downloading a free thing off the store and it didn't work. Is the Itunes store down or am I having a unique problem. If you have an insights that would be extremely helpful as I'm itching to start playing with this thing. Thanks.