It all depends on the speed of your computer. If its slow, and you have a big HD, it will take a long time. If you haven't dont disk clean up in a long time, it will probably compress your hard drive, which takes most of the time. You just have to be patient. I didn't do any hard drive maintence for 3 months, using the utilities such as Clean Up and DeFrag, and CHKDSK took 4 hours.
MY HD was a WD Enhanced IDE 80 GB 7200 RPM