3GS won't update to 4.3.4

[saltrack25]

I tried updating my iPhone 3GS software to 4.3.4 and it says it isn't supported. This is despite the fact that it says it is supported on Apple's website.

http://support.apple.com/kb/DL1418

My last iPhone died when I tried to update to the latest iOS and they gave me a replacement, and now that one won't update (although it still works.) It's not stuck on a screen, it just says it can't do it and then directs me to a webpage:

http://support.apple.com/kb/TS1275

Any ideas? I tried restoring it and then upgrading and it didn't work.

 

[jonrando]

So what happens when you plug in your iPhone to iTunes and click Update?

 

[saltrack25]

It takes me through the normal steps of prompting me that there is an update and would I like to update and downloads the file and then gives me the error. I'm going to see if 4.3.5 works.