3GS iPhone will not update to iOS 5
Simple answer: You don't have a 3GS, but rather a 3G. The last iOS update for the 3G was 4.2.1. A 3GS ran all the way up to 4.3.5, which was the last public release of iOS 4. If you are running 4.2.1 and iTunes doesn't even see the 4.3.5 update, then, well, that's pretty telling that you don't actually have a 3GS but a 3G.