That's the first time I've seen this error.
How many blocks do you have? (in the status bar)
You should move your blk*.dat files (in ~/.bitcoin) to another directory and let it start over downloading the block chain again. If you don't mind, could you keep the old blk*.dat files for a little while in case I need to look at them?