Time Machine Problems

I have an early 2011 Macbook Pro which has been running fine up until a month ago when it became unresponsive the second it was turned on, immediately getting rainbow wheel. Safe mode however worked fine. I booked an appointment at the Genius Bar and went to back up my Mac with Time Machine, only to find that my hard drive had stopped working and all my old back ups on there were lost.

I took it to the Genius bar and the 'Genius' spent around an hour and a half running diagnostic tests and trying to get to the bottom of why my Mac was being unresponsive. He couldn't figure it out and told me that the only course of action would be to buy a new hard drive, use time machine to back it up and then reboot my Mac.

I went about doing this, getting a new 1TB WD 2.5inch hard drive and then entering my user in safe mode and starting time machine. However after completing about 250GB of the 290GB I get this error message,
'The backup was not performed because an error occurred while copying files to the backup disk.
The problem may be temporary. Try again later to back up. If the problem persists, use Disk Utility to repair your backup disk'

Any support would be great.

 

I have ran disk utility multiple times to no avail. It takes around 5 to 10 minutes to complete but reports no issues. I've also used Onyx as a third party piece of software to see if it made a difference but again, no problems come up.

ColdCase, after re-reading my first post I've realised that I didn't word it too well, sorry. The Geniuses said that my internal HD was fine, I just needed to reboot and reinstall Mountain Lion on my MPB. Before I went to the Genius Bar I realised that my portable hard drive, with all of my back ups had broken.
The Geniuses told me to buy a new external hard drive, perform a back up on via time machine and then reboot my internal hard drive. But obviously I can't back up to the external hard drive as my TM is corrupt and therefore I'm reluctant to reboot my internal hard drive. I'll have a read through that link you gave, thanks. I have also tried backing up on to other external drives.