What kind of errors did Disk Utility report? Certain errors on TM volumes can be ignored, like "incorrect icon flag".
A full disk and heavy fragmentation is the most likely explanation. Though the HD could be failing, you can't do much about that. It may show a few GB free, but with heavy fragmentation, most of that free space will be in small KB-sized fragments. Which really slows things down.
First thing: clear some scratch space. Access it via ethernet, to eliminate any wireless questions. Use the Finder instead of the TM interface. Go to:
/(time capsule volume)/Backups.backupdb/(your computer name)/(snapshot folders)/
Go to the oldest snapshot folders, move a few to the Trash, empty the Trash. Assuming you're backing up multiple computers, you might do this step within each computer's folder. note: the Finder will take a long time to empty TM snapshots from the trash.
Repeat as needed until you've got a decent amount free, say 100 GB. Then try Time Machine again. If speed returns to normal, you're done.
If you have iDefrag and/or DiskWarrior, those would be useful to run after you have free space again. They'll also take a long time.