According the iOS 5 features page on Apple's web site, the 3GS is supported. When I push the "Check for Update" button in iTunes, it says "This version of the iPhone software (4.2.1) is the current version." I'm running iTunes 10.5.142 on Windows. I have also used this same setup to upgrade my iPhone 4.
Is there something else I need to do here? Could it be refusing because this phone does not have a carrier anymore and I use it only over WiFi?