Use a lightweight client like multibit or electrum, no blockchain to update. (or at least hope that the new bitcoin client arrives quickly, i am testing it and it download the chain MUCH MUCH faster)
This said...
1)This error is related to the blockchain, sometime the database corrupt and as others said, you need to redownload it, that's why they suggest deleting everything...
2)...but this does not mean deleting wallet.dat! It is where your bitcoins are! Seriously, if you delete your wallet there isn't a lot we can do. And deleting it is not needed to fix the problem
The blkindex.dat and wallet.dat files are in appdata/roaming/bitcoin
Oh and redownloading the whole blockchain with the current client takes days (with the new one takes like 6-9 hours, much less but still a lot)
i've had success occasionally by deleting the database directory and leaving everything else alone (when it gives me that warning)
i'd say maybe 50/50