I'm no expert on the blockchain structure, but I was wondering if maybe some parts you've already downloaded haven't become corrupted. Have you tried running Bitcoin-Qt (or bitcoind) with the -reindex and/or the -checkblocks=0 parameters? (That will take a LONG time, be warned!)