In general, the best thing to do is to run fsck repeatedly until no error messages appear, THEN reboot. Though I'm not 'up' on the nitty-gritty of fsck, I'd assume that sometimes fixing one problem brings another to light, which necessitates a second running of fsck, third, etc.
-Gabe