Every 2 weeks or so my internet would completely go out. However, my internal network was fine and I could ping other computers on the network and access shared files. Additionally, it looked like my DNS server was fine, I just couldn't get out to the internet.
I tried updating the Firmware on my Linksys WRT54G and it still failed.
The only thing that has solved my issue was changing it's firmware, I installed the Tomato Firmware for the Linksys Router and now it works fine.
Look on the bottom side of your router to get the model number, mine was a WRT54G v2.2, before you install the firmware, make sure you have a compatible model.
To update the firmware, you can use the firmware updater inside of the Linksys router admin.