What a difference a simple cleanup and optimization makes! If you are using PhpMyAdmin, follow these simple steps (after safely backing up your data).
Click on the database you are working with on the left hand side frame (not the table, the database name)
On the right hand column your tables should be listed. Scroll down till you see the “Check all” link.
Click on that link, make sure all database tables are checked and then from the dropdown next to it, carefully select “Optimize table”.
This should perform an analysis, repair and an optimization of your database. Most problems will be solved with this. In rare cases you might have to rebuild indices, but thats a huge topic, too dangerous to perform without looking at individual cases and thus I will not preach it here. (My database corruption was one of those rare cases) Please backup your data before any database manipulation and I will not be resposible for any mistakes or loss of data.
PS: Another fairly certain method of fixing your database/tables with PhpMyAdmin is to export your data, delete your existing tables and then re-import. PhpMyAdmin performs certain optimization tasks on the data that are very beneficial.