re: apt-cache bin files getting corrupted
Check /etc/apt/sources.list on both machines. If you are using the
uchicago mirrors for deb and deb-src, that's why this is happening. You
want to switch to another set of mirrors since uchicago seems to have got
itself corrupted. For a little while I had this problem too but cleared
it up by switching to another set of mirrors and running apt-get update.