I'm running Virtualbox 4.1 on an x86_64 Windows 7 host. I've got a collection of 12.04 and 10.04 LTS VMs I use to create debs for work. In the last week I started noticing problems on the 12.04 VMs. Tried the usual apt-get clean bit which didn't help.

I rolled a new 11.10 VM for testing a Worpress upgrade. This VM has never been able to run apt-get update without errors. The interesting errors look like this:

Get: 8 http://security.ubuntu.com oneiric-security/main Translation-en_US [344 B]
14% [7 Sources 48686/877 kB 6%] [Waiting for headers]bzip2: (stdin) is not a bzip2 file.
Hit http://security.ubuntu.com oneiric-security/multiverse Translation-en
Hit http://security.ubuntu.com oneiric-security/restricted Translation-en
Hit http://security.ubuntu.com oneiric-security/universe Translation-en
22% [7 Sources 127526/877 kB 15%] [Waiting for headers]/usr/bin/xz: (stdin): File format not recognized

and ends with

/usr/bin/xz: (stdin): File format not recognized
Ign http://us.archive.ubuntu.com oneiric/main Translation-en_US                                                    
Ign http://us.archive.ubuntu.com oneiric-updates/main Translation-en_US                                            
Fetched 18.5 MB in 47s (392 kB/s)                                                                                  
W: GPG error: http://us.archive.ubuntu.com oneiric InRelease: File /var/lib/apt/lists/partial/us.archive.ubuntu.com_ubuntu_dists_oneiric_InRelease doesn't start with a clearsigned message
W: GPG error: http://security.ubuntu.com oneiric-security InRelease: File /var/lib/apt/lists/partial/security.ubuntu.com_ubuntu_dists_oneiric-security_InRelease doesn't start with a clearsigned message

xv-utils, lzma, etc are all installed. I've reinstalled the VM from scratch three times and up at the same point.