DiskWarrior could not fix the problem. I'm thinking the drive has a mechanical problem.
Oh well, no more Maxtor drives for me as the failure rate is now 2 of 2 for 100%.
UPDATE:
After running a directory rebuild again, it looks like DiskWarrior has indeed come through.
I am backing up the drive now.
