I would recommend getting the Diagnostic Utility for the drive that you have. (I am pretty sure "ALL" manufacturers have such a utility. I know Western Digital and Seagate do.)
Generally, when you get the message "Trying to recover allocation unit" it means there is damage on the hard drive.
During the format process a very quick test is done on each sector on the hard drive. If this test fails, or is suspect, then the program tries several times more. This has a "VERY" noticeable affect in the speed of the format operation. Ultimately if the test fail that sector on the hard drive is marked as "BAD". Once marked as "BAD" the OS will avoid using that location in the future.
Now the damage to the hard drive may be localized, and it may be that once the drive has been formatted it will work fine for many years.
In the past, I have had that specific scenario occur many times. With current hard drive technology this error has quite nearly "ALWAYS" been a harbinger of near term failure.
Since you are reformatting the drive, I would presume there is very little data that would be lost at this time!
I would try to replace the IDE cable just on the off chance the cable is damaged and causing some of your problems. (Usually if the IDE cable is bad then the drive doesn't work at all, but you never know?)
If that doesn't fix the probelm replace the drive.