Comment 122 for bug 1073433

I'm experiencing similar issues on an EXT-3 filesystem. There are no inode/block errors reported by fsck but the root filesystem (/ is mounted on /dev/sda2 in my case) fails the fsck check at boot.

% dmesg | grep sda2
EXT3-fs (sda2): recovery required on readonly filesystem
EXT3-fs (sda2): write access will be enabled during recovery
EXT3-fs (sda2): recovery complete
EXT3-fs (sda2): mounted filesystem with ordered data mode

[Edited for brevity]

This happens on every boot. The other partitions (and there are 6 including swap) all pass the fsck check.

The workaround of deselecting "Available to all users" in Network Connections discussed above works for me. Seems reasonable to assume that this is not filesystem specific and that the shutdown is not clean for some reason.
Quantal 12.10
Linux 3.5.0-28-generic #48-Ubuntu SMP Tue Apr 23 23:05:48 UTC 2013 athlon i686 GNU/Linux