Macbook boots up to grey 'prohibited' symbol
There are times when Apple's 'Disk Utility' software isn't as thorough at repairing problems that other applications may be.
I've had 'Disk Utility' tell me that drives are fine, but it is not until after running a program like 'Disk Warrior' (that replaces the Directory structure), that the hard drive feels 'normal' again.
This isn't to plug any particular software, but to let you know that 'Disk Utility' isn't the be all, end all of determining if a hard drive is 'good'.

Given your description of the problem, I'd be inclined to make sure I had a backup. If not, purchase a new hard drive, and get all the data off of the old one as quick as possible. (I agree with @Asmus that it appears that you are about to lose a hard drive).

On the other hand, you may just need to have the mac reinstall the OS, and fix things that way. Either way - make sure you have a solid backup right away.

Good luck.