Here you can find the inspiring post for this solution: http://www.megacomputers.com.my/version2/content/warning-mysql-server-ha...
Here's another one: http://drupal.org/node/259580#comment-1511512

Anyway the whole idea is this:

1. Quick approach (not recommended since it will leave you with no module update information)
Just go to Admin -> Site Building -> Modules and disable the 'Update status' module.

( Sometimes, this is the only thing that works)

Anyway you will be left without actual information on any new updates or new major versions for your Drupal and modules.

2. The real fix (requires hacking of 2 Drupal core files)
Here is the real solution, it will require you to get hands dirty, but will fix your problem.

First make a backup of these two files - just download them to some directory so you have them just in case:
includes/database.mysql.inc
includes/database.mysqli.inc

Now you need to edit these two files (I edit them directly on the FTP server, but you can make additional copies locally, edit them, save and then upload back)

Add the following lines of code (on a new line, as explained):
In includes/database.mysql.inc, at the end of function db_connect(), under the "SET NAMES" line:

mysql_query('SET SESSION wait_timeout = 60', $connection);

In includes/database.mysqli.inc, at the end of function db_connect(), under the "SET NAMES" line:
mysqli_query($connection, 'SET SESSION wait_timeout = 60');

Now you should get no more MySQL errors.
If you increase the number of istalled modules on your Drupal you may need to increase the timeout from 60 to a bigger value, for example 90, but I seriously doubt it will be ever needed.

The idea of all this is that the update module will require more and more time to check for updates for the increasing number of installed modules on your Drupal site. At some point this time will exceed your server's default value for timeout and this causes MySQL "server gone away" errors.

On many webhosting companies' servers this timeout is set to a very low value (too conservative) and that's why so many people are facing this problem.