I did a bit of a search and found a fix that worked for me, and was pretty simple. There are two files that apt creates, that somehow got corrupted. On my system, they are called pkgcache.bin and srcpkgcache.bin, and they live in /var/cache/apt. I tried moving them to another directory, and re-running apt-get update, and what do you know, it worked! I later deleted them, as there was no need for the old copies.
For those who don't want to move the files before deleting them (I recommend that you at least copy them somewhere else, just in case), the command is:
sudo rm -i /var/cache/apt/*.bin
The command should ask you to remove two files - it does in my case. I chose to put the "i" switch in the rm command just to be sure to prompt you before deleting.
(Originally posted September 12, 2009 on my other blog)