The Verify and Repair Disk options are meant for when files become corrupt, not for permissions errors. You can't repair the disk you booted from, so this option is grayed out unless you boot from another disk (like the OS X Install Disc.) With the Journaling file system, verify and repair aren't as useful as they once were, since the OS automatically repairs the file system if it detected an improper shutdown, and journaling makes these types of errors much less common.
If you want to play 'ultra-paranoid', boot from your OS X Install Disc, run Disk Utility from there, and do both "Repair Disk" and "Repair Permissions".
Although there is some talk that repairing permissions is nearly useless.