Can you tell us what your old router is? Make and model? Then we can see if it already has features that we would be recommending that just aren't cutting it in your current setup.
If your old router is a wireless G router, then upgrading to a wireless N router will improve your network's range.
But this is also dependent on your devices being wireless N compatible, else you'll need to upgrade them as well.
Sometimes simply relocating the router to a more central location in the house will provide better coverage for your home.
Another option would be to get a second router for the other end of the house and pipe the network there via one of those clever AC network adapters.
Just a couple ideas. We can fine tune your solution based on what you currently have.