I observed this after upgrading PhpGedView and my server from Debian Lenny to Debian Squeeze at about the same time. I don’t know what was the root cause. “SHOW FULL PROCESSLIST;” was a very useful SQL command to see what the database was grinding on. Looked like an innocent enough query to me.
I made a few changes to my.cnf inspired by some random web searches (key_buffer=128M in 2 places, and query_cache_size=32M in one place), and then dumped and reloaded all data. This helped a lot. The response time became much more reasonable, and the database has not crashed or otherwise become unresponsive.
# Dump all data
mysqldump -u root -p --all-databases --opt > all_databases.sql
# Re-input all data
mysql -u user -p < all_databases.sql