Monitor the internet connection via shell script, and power cycle the modem with a couple of X10 home automation modules fit the internet is unreachable.
I did a google search for "linux x10" and found Heyu (http://heyu.tanj.com/), an actively developed set of tools for the X10 protocol in linux. Looking at the supported devices, i popped a couple of those in to amazon, and a few days later, i had myself a CM11A and an LM14A module.
Some people (Eric and Neil) are saying that the LM14A may not be appropriate for this job. Personally, i find that it's working just fine, and i'm not to concerned if it lowers the life of my modem - at that point, i'll replace it. This added functionality is worth it, and the functionality comes with minimal input effort. Read the comments if you are concerned that the LM14A may reduce the life of your modem. Additionally, GrinningArmor advises, "Any X10 module being plugged to the battery-powered output of an UPS is not likely to work, and could be burnt," and i agree with him. Your mileage may vary, but please be aware of these factors when making your decision on implementing this solution, and when choosing a module.
The CM11A plugs in to the computer via serial port, and the LM14A simply plugs in to the wall. The modem is then plugged into the wall module, and we are, for the most part, done. The wall module needs to have an address, and I left this module set to A1 for simplicity. (Further details about the X10 system are out there; they are simply beyond the scope of this document.)