3.1 didn't fix it, but
I wish I had read this before I went back to the Apple Store for the third time.
So, this is what happened to me.
When I switched from a belkin to a Time Capsule, my 3GS started having major connection issues. I did everything I could think of, then called AppleCare. They had me repeat some steps that I had done, then told to make a Genius appointment.
The Genius couldn't see the problem, but she replaced my phone anyway.
The new phone had the same wifi issues, PLUS touchscreen issues.
Back to the Apple Store.
This "Genius" told me that he couldn't find a problem, and maybe it's with the TC (even though everything else connects to the network just fine). Told me to bring that in for another appointment.
I went home and called AppleCare again. This time, she had me do the same stuff on the phone, and then made another Genius appointment for me.
Back to the Apple Store. The Genius saw and fixed my touchscreen issue (hallelujah!!), but couldn't figure out the wifi thing. Suggested everything I had already done. Told me to go home, call AppleCare once more, and then come in with my TC and my iPhone for a diagnostic on both.
I go home, call AppleCare, she has me repeat two steps, and then transfers me to a Time Capsule specialist. He asks me everything I've done, tells me to change the channel on the G network, and voilá!
That was about nine hours ago, and my iPhone hasn't lost the comnection once (fingers crossed).
All the suggestions for resetting everything under the sun, and consults with half a dozen "specialists," and no one thought about the channel. I had done more on my own than anyone had suggested, and I didn't think about the channels.
I live in a 64-unit condo with networks all around, visible and invisible. It wasn't an issue with my old Belkin, or my 3G, but the combination of the Time Capsule and the 3GS was a perfect storm, I guess.