I have noticed similar errors before.
It could have been caused by shutting down the machine wile it was still updating the blockchain or updating any number of other files I believe.
You could try removing all of your blkindex.dat files and re-downloading the block chain. Couldn't hurt.
Yes, I had to shutdown (somewhat) disgracefully yesterday because I assigned too little ram for my virtualbox guest and it halted. On another bitcoin client that I'm not running on this virtualbox client, I'm not getting this error message, so I presume you're right. Thanks!