I've run into the same problem today, but only with some configurations:

1 x dual core intel - one big reiserfs disk - no problems
1 x dual core amd - one big reiserfs disk (/) and two xfs disk for storage - no problems

Kervel (https://bugs.launchpad.net/ubuntu/+bug/133786/comments/24) who also works here:

1 x thinkpad laptop - ext3 /boot, the rest xfs partitions - corruption
1 x macbook pro - ext3 /boot, the rest xfs partitions - corruption

And this morning a new server:

1 x two cpu, dual core intel, ext3 boot, the rest xfs on a software raid 1 - corruption

All systems are completely updated and fresh installs. 

debsums: checksum mismatch git-core file /usr/bin/git-mktree
debsums: checksum mismatch gsfonts file /usr/share/fonts/type1/gsfonts/n019023l.pfb
debsums: checksum mismatch libc6-dev file /usr/lib/libc.a
debsums: checksum mismatch libc6-dev file /usr/lib/xen/libpthread.a
debsums: checksum mismatch libsnmp10 file /usr/lib/libnetsnmphelpers.so.10.0.1
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/kernel/drivers/isdn/hisax/hisax.ko
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/kernel/drivers/net/wireless/ipw2100.ko
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/kernel/drivers/scsi/aic7xxx/aic7xxx.ko
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/kernel/drivers/scsi/ipr.ko
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/kernel/fs/gfs2/gfs2.ko
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/modules.pcimap
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/modules.dep
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/modules.usbmap
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/modules.isapnpmap
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/modules.alias
debsums: checksum mismatch linux-image-2.6.22-14-server file /lib/modules/2.6.22-14-server/modules.symbols
debsums: checksum mismatch mc file /usr/share/locale/tr/LC_MESSAGES/mc.mo
debsums: checksum mismatch mysql-client-5.0 file /usr/bin/mysql_client_test_embedded
debsums: checksum mismatch mysql-server-5.0 file /usr/bin/ndb_delete_all
debsums: checksum mismatch mysql-server-5.0 file /usr/bin/ndb_drop_table
debsums: checksum mismatch mysql-server-5.0 file /usr/bin/ndb_select_all
debsums: checksum mismatch mysql-server-5.0 file /usr/share/mysql/mysql-test/suite/funcs_1/r/myisam_views.result
debsums: checksum mismatch python-egenix-mxdatetime file /usr/share/doc/python-egenix-mxdatetime/mxDateTime.pdf.gz
debsums: checksum mismatch sun-java6-bin file /usr/lib/jvm/java-6-sun-1.6.0.03/jre/lib/rt.jar
debsums: checksum mismatch ttf-dejavu-extra file /usr/share/fonts/truetype/ttf-dejavu/DejaVuSansCondensed-BoldOblique.ttf
debsums: checksum mismatch xfonts-base file /usr/share/fonts/X11/misc/18x18ja.pcf.gz

Other lines were for examele

debsums: no md5sums for at
debsums: no md5sums for base-files
debsums: no md5sums for binutils
debsums: no md5sums for bzip2
debsums: no md5sums for dosfstools
debsums: no md5sums for ed

I went to install a custom kernel and installes the following programs as to the tutorial in the Master Kernel Trhead on the forum:

sudo apt-get install build-essential bin86 kernel-package libqt3-headers libqt3-mt-dev wget libncurses5 libncurses5-dev

after his both "at" and "binutils" were corrupted. Reinstallation of these packages fixed it.


So, the comment above has some merit i believe (since a clean install + updates corrupts) but the ext3/xfs - reiserfs difference seems a big coincidence?