|Well, if the troubleshooting doesn't fix it then yes, it's probably time to get a new router.|
And apparently Tomato doesn't work for my router, either.
I mentioned Tomato 3'd Party Firmware with regard to the router you mentioned buying (WRT54G) not the one you have (Linksys BEFW11S4) which isn't capable of using 3'd party firmware.
If you click on the Tomato link I posted above, that pages lists all compatible routers.
There is also a VPN capable version of Tomato and if you're interested in that one (providing you buy a compatible router) then you'll have to google "Tomato Firmware"+VPN to find it as it's not on the page above.
It matters not how straight the gate,
How charged with punishments the scroll,
I am the master of my fate;
I am the captain of my soul.