I Think the first thing wold be to download and run NetStumbler (
www.netstumbler.com it's free).
What that will show you is what channels are used and what the interference level is in your area. Choose the least congested channel out of 1, 6, or 11 (choose the least congested, least interfered-with from one of these three only).
If "upstairs" and "downstairs" are both PCs (not laptops), then run NetStumbler at both computers, and choose; channel interference and noise could be very different for each system. If either system is a laptop, then just wander between the two spots while running NS.
Next, verify your wireless security (WEP, WPA). If you're using MAC filtering or have SSID broadcast disabled, turn em both on, they're not helping security at all. If you're using WEP, reconfigure and start using WPA (probably WPA-PSK) ... the point being that you may be unintentionally sharing your bandwidth with some asshole parasite of a neighbor.
If your AP / Wireless router doesn't do WPA, personally, I"d scrap it. If you can't, then at least change the SSID every week or so (or when you notice the system slowing down again).
Next, run Ad-aware and spybot Search & Destroy (both are free)
If none of the above help, then I guess we'll talk about the specific of your machines.
Good Luck
Scott