I've tried repeatedly to update my iPhone 4S to OS 5.1 but always get the message that I "cannot connect to the server..." I've tried over the air and I've tried thru iTunes, and have never been able to connect.
A number of people here and on the Apple Support forum have reported changing the DNS server on your phone to 8.8.8.8 and it seemed to allow for it. I guess that is something you can try.
Thanks so much for pointing me in the right direction. After reading your response I did a little more research on Apple Support and eventually added 2 more DNS:
208.67.222.222
and
208.67.220.220
Tried upgrading again OTA and once again got the "Unable to connect" message, so I tried again through iTunes and FINALLY it worked!