Have you tried running it out of the Windows environment? If you have an install DVD that you can boot to (or a Startup Repair option via the F8 Safe Mode screen), try launching the Command Prompt from the options provided when you go down the Startup Repair path.
Do not perform the Startup Repair, just look for, and go to the option for the Command Prompt (from the Choose a Recovery Tool dialog), and try running Chkdsk from within that.
Startup Repair: frequently asked questions
How to use the Command Prompt in the Vista Windows Recovery Environment