jamesmcd: Looks pretty good (the TD-W8960N). Any idea where I can buy one of these? More importantly though, what can you say about its wireless range? Will it comfortably go upstairs? We've got a 3 level house, with the router ideally in the middle. It's not actually far to the upstairs at all, which is why I'm so disappointed at the modem from Telecom. Our old D-Link has trouble getting up there too. It's literally directly upwards from the router, about 6-8 meters, and modern devices struggle to see it and often can't join.
If there is something in your ceiling/floor that's causing interference (metal, lead paint etc) then a new router may not help as much as you hope.
Try the new unit, if it's still a problem I would look at running a network cable between floors (or using homeplug networking over the power wiring) and have a wireless AP on each floor.