Back in November I started getting an error on TimeMachine that made backing up spotty best if not impossible. I started searching around the next to see if anyone else was having the same problem. I eventually found someone that was and found a fix for the warning I was getting.
Shut the computer down
Hold down Command+R keys (If you have hardware protection set, enter password.
Once you see this you can then figure out what you going to do. Restoring From TimeMachine reformats your HD.