. . .
I then ran Verify to confirm and came back with Verify Failed, Invalid Directory Count, should be 38 instead of 39, and should be 47 instead of 45
You need to repair the file system on your HD. See the yellow box in #6 of Using Disk Utility.
In rare cases, Verify Disk can report spurious errors (it's quite a trick to compare everything while OSX is running). See Mac OS X: Disk Utility incorrectly reports disk errors on startup volume.
That article doesn't mention Snow Leopard, and reports of the difference are quite unusual here. I can't recall seeing one in several months. And for it to be consistent is pretty hard to swallow, too.
Plus, your report of your system crawling and getting noise from the HD seemed to implicate the HD.
You might want to run this: Intel-based Macs: Using Apple Hardware Test. Run the Extended tests (that may take an hour or more, depending on how much RAM you have). Write down any error code(s) it shows.
You might also want to compare the noises you hear to these: http://datacent.com/hard_drive_sounds.php
Verify while booted from the startup disk is using "live" verification, which can be inaccurate. Boot again from another volume or the install DVD and try verifying again from there. If it shows the same error, then something is genuinely off. If not, then disregard the results from live verification.
In addition to Pondini's suggestions, you can check the health of the drive with the free demo of SMART Utility. It runs a pretty exhaustive check and might be more accurate than the Hardware Test, which is not really known for accuracy.