Are you running chkdsk from the command line or from the GUI tools option for the hard drive? If from the GUI, try to use the command line instead. You just need to enter the drive letter like so:
chkdsk C: /R
Try the R switch (it implies F also) and see what results you get.
I forgot to mention that you can temporarily disable the windows restore service to free up some more disk space when trying to defrag and also, using the disk cleanup wizard, you can delete the restore points already on your disk.