We're in an old rock solid 3 story house too. From the technical material I've read, you will get the best wireless coverage if your transmitting router is in the basement.
Now, if that's not feasible (our situation), you would do well to get a MIMO-type wireless router and receiver like Netgear's RangeMax (or its even better success which just came out recently). Our notebook got lousy reception on the first floor and basement until we switched to Netgear's RangeMax equipment. Now the signal comes through loud and clear.
I understand that wireless equipment is starting to be released that is based on the new wireless N standard -- which should provide greater range, signal strength and security. Go to pcworld.com for articles on this. I'd recommend sticking with Netgear and avoiding Linksys whose technical support is unbelievably bad (as in just plain wrong advice, mislabeled firmware and application upgrades to download -- and a language barrier that makes it rough on customers who speak English as their native tongue).