Ok, so to reiterate the flow here:
You go to itunes, click to update the phone, it downloads, then tries to do the update and THEN it gives you the can't contact update server message?
For some reason, you're having a problem getting to gs.apple.com from your computer. A lot of jailbreaks use a line in there to prevent iTunes from validating with the Apple servers. Not sure why it would be there if you wren't jailbreaking though. I don't have a mac, so can't help you in locating the file and looking at it, but you need to check your hosts file for gs.apple.com, just to make sure it is not there.