Disabling the Update Status module made my "MySQL Server has gone away" errors go away for a little while. But then it came back. Along with the errors, the cron job wouldn't complete, and therefore the cron_semaphore (do you know what a sempaphore is?) variable in the variable table wouldn't reset, and thus cron wouldn't run again. I talked to Site5 support - they have added instant chat support since the last time I had a major issue - and they got it fixed by upping the MySQL memory limit in a my.ini file that contained the following:
Apparently you can modify the MySQL settings as well as php.ini this way. Nice.