Did you use Disk Utility on the "Macintosh HD" partition or for the whole drive?
It still sounds as if something's up with your startup disk (partition). Try running Disk Utility again. If still no errors, try resetting SMC. No joy? The Apple Hardware Test. Still having trouble? Time for a trip to your local Apple Store or AASP.