Can you boot the machine now? if so, run Disk Utility and 'fix disk permissions' and also see if the disk is OK...
If you can't boot at all (and posted the above message in another machine!), start the machine from the OS X CD and use the same procedure as above. See if it fixes the problem.
Hope this helps,
Peace,
Marc
(If you want to go all *nix, restart in single user mode (Hold Apple and S on restart) and run fsck... although if you aren't confident with this I wouldn't bother...)