What to do when my Time Machine drive is getting disk errors?
It sounds like you might be out of luck if Disk Utility was unable to repair your partition. You are also correct that a clone of your Time Machine partition would copy over the problem to a new drive. It is probable that your best "solution" at this point would be to erase the partition and start Time Machine backups again. If you end up doing this I would also make sure to run "Verify Disk" on your internal HDD (or SSD if that's what you have) to make sure there aren't any errors there, either. 

This might be a symptom of a failing drive; however, it is also possible that it might simply be a bunch of directory errors that can be repaired if you boot from a recovery partition, clone, or use another Mac to repair. I have had both dying drives and drives that looked like they were dying, but were actually just errors piled on one another. Before you throw the drive away, try repartitioning. Do systematic checks with Disk Utility and keep an eye on system logs (either in Console.app or /var/logs/system.log). If you continue to see the same problem, then it is indeed time for a new backup drive; however, you might find that a quick erase fixes the issue. 

Also, see this article over at Pondini.org. The article essentially corroborates what I've already said, but the rest of the site is an excellent resource for all the headaches that Time Machine can throw your way. 

Sorry you have a bunk backup - hope you get it sorted without much extra trouble!