The symptom you describe is how a phone that was hacked to unlock it would behave. Did you buy it directly from an Apple store or Apple online, and does the receipt say "unlocked"? Or is it a used phone, or purchased from an independent shop?
It can also indicate that the computer you are using was used to hack some iDevice, not necessarily the one with the problem, and the process corrupted the network database on the computer.
The other common cause of a failure to activate is antivirus or firewall interfering with access to gs.apple.com.
I have a 3gs that I had unlocked through AT&T and checked it through apple. It wont go past the activation screen. Apple server is unavailable please try again. I was on the phone for 3 hours with different people last night at apple and none of them know how to fix this. The last person told me she has to get in touch with the engnieers in order to fix this. The thing that I dont believe about this is that I just had the same problem with another 3 gs a couple weeks before and after being ont the phone with apple for 2 hours and talking to different people I finally talked to someone that knew how to fix it. I hope someone can help me with this. I do not want to Jailbreak it. It is unlocked. Thanks
I've already posted the causes, but in case you missed them in the first post:
1. Your antivirus is blocking access to gs.apple.com.
2. Your phone is jailbroken.
3. Your computer has been used at some time in the past to jaibreak some iOS device (not necessarily the phone with the problem), and its network database was corrupted by the hacking software that was used.
4. Apple's activation servers are down (very rare, and never for more than an hour or so).
For 1. try disabling your antivirus.
For 2. & 3. you need to go somewhere other than an apple forum for help. Although you can try deleting lines containing gs.apple.com from your "hosts" file on your computer.