Connect to your external hard drive via USB, Firewire, or Thunderbolt.
Problems can occur when backing up over a network connection that corrupt the time machine backup.
This apple support communities discussion ended menitoning the Airport Extreme Base Station as a possible cause of the problem.
This site goes into more detail about the error message.
Time Machine locks the sparse bundle containing your network backups, and marks it as damaged. You may be able to view and restore some things from these backups, but you will not be able to continue backing-up to them. Disk Utility may appear to repair them, but they’re still damaged and if you try to back up to them again, you’ll just get the same message again.