That 'manually run fsck' message should only appear after an unclean
shutdown... How are you rebooting/shutting down?
Otherwise for lucid make sure to have "fixrtc" in the bootargs, but
this only works when using an uInitrd with your uImage... Next can you
dump your fstab to pastebin.com?
Regards,