It may just be plain ol' interference issues. One of the problems w/ wireless is that the 2.4GHz freq is not reserved for wireless routers. It's an "open" freq available to just about anyone/anything who wants to use it. That includes microwave ovens, cordless phones, baby monitors, wireless keyboards/mice, etc., and of course, other wireless routers. The fact it didn’t change when you replaced the router further suggests it’s interference.
Did you try placing the router in another location (preferable centrally located), and/or elevated by a few feet?
Do you have any unusual environmental conditions? I once lived in an house w/ plastered walls that were so old and hard, they had been virtually petrified! Trying to get wireless signals around the house was like dealing w/ lead walls!