Windows 8 hard disk usage 100%

This is a problem I've seen described in many places:

• Super User (here, here, here and so on)
• Microsoft support forums (here, here…)
• The Lenovo forums have some users complaining about this too (here).
• Tom's Hardware (I'll spare you the links due to ads)

Unfortunately, none of the solutions there have worked.

In short: even with only system processes running, directly from a boot, the hard drive usage goes to 100% and remains like that for an excessive amount of time. By that I mean, roughly 30 minutes before it drops back to 0%, and then any usage (eg: opening chrome) sends it back up to 100% for a long time.

The amount of data being read from/written to the disk is minuscule (usually under a couple hundred kb/s), with enormous latency, usually upwards of 5000ms.

During this time, the computer is entirely unusable. Going back to the classic desktop can take minutes. Trying to launch (not actually launching, but just typing the name of a program to launch) can take minutes. Even booting and shutting down can take 5-10 minutes.

Full size image here

About the computer: It's virtually new. Bought <6 months ago and only used as a gaming PC. The only applications I've installed are VLC & Chrome, along with Steam and several games. 8gb RAM, 1TB HDD (750GB free), Windows 8 came pre-installed.

I have tried almost everything suggested in the various forums and links above:

• superfetch is disabled
• I've done a clean boot
• I've disabled hibernation support
• The virtual memory is set to 8000mb initial size and 16000mb maximum size
• I've disabled all startup processes and all non-microsoft services
• The power management is set to high performance
• The DVD drive is disabled (wtf I know, but I'm desperate here and someone said it helped)
• chkdsk has been run and found no errors
• The computer is up to date with Windows Updates

This just started happening about a month ago, where it would be very slow for < 1 minute and then would work fine. And then in the last week, just using the computer at all has become impossible. Prior to this, the computer would boot and be ready to go in about 10-15 seconds.

Perhaps frighteningly, I can actually hear the hard drive 'clicking' somewhat when the system shows the hard drive at 100%.

Does anyone have any ideas for me?

Update:
I've booted onto a LiveCD version of Ubuntu. Here, browsing around the hard drive in Nautilus is snappy, but it's not really running under the same conditions, I suppose. Overall, it's very fast though. I ran a full S.M.A.R.T. scan which brought these results. I don't really know how to read these, so some help here would be really nice.

• 1 Read Error Rate: Normalized: 100, Worst: 100, Threshold: 51, Value: 818
• 2 Throughput Performance: Normalized: 52, Worst: 52, Threshold: 0, Value: N/A
• 5 Reallocated Sector Count: Normalized: 252, Worst: 252, Threshold: 10, Value: 0 sectors
• 7 Seek Error Rate: Normalized: 252, Worst: 252, Threshold: 51, Value: 0
• 200 Write Error Rate: Normalized: 100, Worst: 100, Threshold: 0, Value: 3953
• 225 Load/Unload Cycle Count: Normalize: 98, Worst: 98, Threshold: 0, Value: 28705

This is the result from a Read-only benchmark:

Update

I eventually gave up and sent it back to Lenovo. Their assessment was that the hard drive was defective and there was apparently "something" wrong with the OS too. The machine was just returned with a new HDD.