Can not upgrade to iOS 5.1
It turns out you might need to set your DNS server to 8.8.8.8 as I found out Here.

To change DNS settings, go to the Settings app and then pick Wi Fi in the left column. Tap the blue arrow that's on the right of your Wi Fi network name, and DNS should be an option, and you'll see a number like 198.0.0.1. Tap this number and change it to be 8.8.8.8.

Try the update after changing the DNS setting (wait a minute as you'll have to reconnect your wireless connection) and the update should work now.