Yeah, you can't repair the startup disk while you're booted from it. You'll have to boot off the Install CD.
You can also run fsck manually (it's the Unix command that's run when you verify or repair a disk). Boot your Mac into single-user mode by holding option-s during startup. Once you're at the command line, type fsck -y or fsck -yf if the drive is journaled. After the scan/repair is done, type exit to continue booting.
You may have to turn journaling back on afterwards; I can't remember.
Oh, and the system runs fsck while booting, so it's not really necessary to run it yourself unless you're experiencing problems.