Ok, just wanted to add my two cents.
I have been having all the same connectivity issues listed above. I actually bought a be Motorola SB6121 cable modem and updated my old Airport Extreme to a new 5th gen edition. My iMac Internet works great, and my grandmother's iMac works great downstairs. Other external devices, however, were having connectivity issues, my PS3 and my iPhone 4s in particular. I tried changing channels and this provided only about 10 minutes of relief as mentioned above. I reset everything a number of times, nothing worked.
I did some research on the PS3 issue and found a thread that instructed me to enter a specific dpna ID, and voila! Problem solved. I suspect that this issue may have been related to the new network, but I am not positive. This left the iPhone issue.
On a whim, I decided to setup a guest network on my Airport and try that. For whatever reason, this has fixed my problem, at least temporarily. I have been logged into the guest ID all day and it is still cruising. This may not hold for the long haul, but thus far I am having great success.
I figured I'd share this for those of you who may be more knowledgable than me and might be able to determine something from this workaround. Also, for those of you, like me, who have limited network comprehension, but would like at least a temporary fix for your wifi.
Thanks Jim