1. boot with the kernel command line: init=/bin/sh since debian's single-user mode gives you most filesystems already mounted.
2. run fsck (read the man page to give you the options appropriate to your root fs); run it on all your filesystems.
3. shutdown -h and power-cycle.
4. run aptitude update then upgrade anything required.
5. reboot. Watch the screen for any errors on shutdown that would suggest that the system isn't, e.g. remounting the / fs ro before halt/reboot. If in doubt, set up a serial console and log the output or set up the console output to go to a printer.
6. If you still have problems, boot knoppix (I use grml) and run fsck. If this is ext2/3, I'd run -c -c so that the entire disk gets read to force the drive firmware to re-map any bad sectors.
While this is running, I'd be watching /var/log/syslog for any errors from the drive.
7. Ensure that you have SMARTmontools installed and run a long smart test and when its complete, check the results on the drive.
If all else fails, plan for a reinstall (ensure that you have backups).
Then boot knoppix and run wipe on the drive. This fully exercises the drive to exorsize any gremlins. Then install etch minimal (don't select any tasks), ensure that aptitude is installed (if it isn't, then apt-get aptitude), get aptitude set up the way you like with only necessary packages marked as manual, the rest as automatic, then do an update and upgrade before you install any other packages.
At each stage, do a