Hey guys!
I had this problem too.
Whenever I tried to run check disk (right-click C drive, properties, tools, check now), I was always told that it could not run and would run on the next start-up.
However, it NEVER did.
I followed numerous ideas, both here and on Microsoft Newsgroups, and NOTHING (!!!!) helped.
I even re-installed Vista, to no avail.
Just today I came across this link.
WinVistaClub : ChkDsk does not run at startup in Vista
I followed his instructions.......and PROBLEM SOLVED.
I'm posting this so that next person who can't get this problem fixed should know about this option.