What version of bitcoin are you actually running, where did you get it from, what OS? and can you look for INVALID in your debug log and post the few lines before and after the first instance of that?
I am running bitcoind on Debian Wheezy/Unstable, and according to debug.log (though I thought I saw 0.8.4 in the git pull):
Bitcoin version v0.8.2-332-gf19eda1-beta
It doesn't say INVALID in debug.log anywhere - could something else cause the inconsitancy? Or can I git my way back to a better version of bitcoind?