Arkroyal,
The reason I wanted to run the error checking because enough corrupted data on the Hard Drive can lead to the very clicking sounds you are hearing. 99.9% of the time it is a Hardware Issue, but I wanted to be sure before we replace the Hard Drive.
Have you thought about which Hard Drive to replace it with? (You want at least a 7,200rpm Hard Drive with an 8Mb Cache on it.)
Take Care,
Richard