Also 65000 Einträge sind normalerweise für MySQL kein Problem!
Ich tippe mal auf ungünstige Programmierung (keinerlei Optimierung bei Queries) ...
Wenn Du in Deinem mysqld das Slow Query Log aktivierst (
http://dev.mysql.com/doc/mysql/en/Slow_query_log.html ), könntest Du schon mal die "böse(n)" Abfrage(n) herausfinden ... (und zur Not hier zur Diskussion stellen).
Michael