It's hard to identify one particular thing it could be without knowing your system and watching it. I'll give you a bunch of "it could be" type things to look at. These are not in any particilar order, FYI.
Check your version of MySQL. There have been a few table corruption bugs fixed lately. 4.0.18 is the most recent. You'll want to be sure you are new than 4.0.14 as it had an idex corruption bug that really hurt a lot of our users.
Are you running low on memory on that database? Is it thrashing to disc too much? Is it out of tune?
this discussion and
this discussion are great resources to get you going.