Has anyone else faced a problem like this?
If powerline adapters work, they are great. If not, they're a royal pain to get working, and deserve throwing out.
My first point would be like Andrew: use a cabled ethernet backbone down the house, with small switches on each level, and a WiFi access point on that level, for that level.
If fixing wiring in place is going to be hard, consider workarounds. At the moment, I have one leg of our backbone using a flattened patch cable, that routes carefully through the seals in the windows, up the house behind a drainpipe, and back inside through another window.UV will kill it off sooner or later, but it was a quick fix.
Second would be to give up on using the WiFi built-in to the router. Any router. You want to give up on consumer-level WiFi, and step on to the entry-level enterprise-grade stuff.
Andrew pointed at links to Ubiquiti Unifi access points, which are a good entry point for this.
An alternative to a (wired-backbone + WiFi) plan would be one of the newly-released mesh WiFi setups. There, you buy a pack of 3 WiFi APs, which create their own wireless backbone using, if I figured it correctly, separate radio channels for the backbone and for the end-users.
This wireless backbone would probably depend on you getting good connectivity from one floor to the next on 5GHz, so might not be really suitable.