Time Machine - Troubleshooting
A5d. How to Repair Time Machine Backups
on a shared drive connected to another Mac
Backups performed over a network are stored in a container called a sparse bundle disk image on the external disk (different from the way they're stored if done directly to the disk).
First, use Airport Utility to disconnect all users (see section #C12 for instructions).
The best and fastest way to repair backups on a disk in or connected to another Mac is to repair it from that Mac. Or, if it's an external HD, you can connect it directly to your Mac.
Either way, use the Disk Utility app (in your Applications/Utilities folder, or type Disk Utility into the Spotlight search box in your menubar).
Then repair the partition on the disk (and, if you're on Lion 10.7.x, the partition map), per section A5a. That should only take a few moments.
Open the external HD via the Finder, 
locate the sparsebundle for the Mac in question, and drag it to the Disk Utility sidebar. It may take a few moments for it to appear. (Note that the "sparsebundle" in the name may not be shown.)
Select the sparse 
bundle in the sidebar, click the First Aid tab near the top, then the Repair Disk button.
If the Repair Disk button isn't enabled, and the "Time Machine Backups" disk image is shown below it, select the disk image instead.
Don't click the Verify Disk button first; if a problem is found, and you then click Repair Disk, the entire verification is repeated!
(If you get a message that the sparse image is in use, or can’t be unmounted, see section #C12.)
Repair Messages
When repairing a 
sparse bundle, the messages may not appear in the center area of the screen. Click the Log icon in the toolbar, or select Window > Show Log from the Menubar to display them.
What you're looking for, of course, is the "appears to be ok" message. If you get error messages instead, see the pink box below.
Note that this log is kept on your Mac, so if you missed the messages, you can start Disk Utility again and go directly to them, without having to run Repair Disk again. Each task is separated by a row of asterisks.
If an external HD isn't in the sidebar:
See If a disk doesn't appear in the sidebar.
If Repair Disk fails:
If Disk Utility says it can't repair the sparse bundle, look closely at the messages. If it repaired some things, but not everything, run it again (and again) until it either repairs everything or can't repair any more.
If Disk Utility can't repair the sparse bundle, it's possible a heavy-duty 3rd-party disk repair app, such as DiskWarrior, can. These are expensive (DiskWarrior is about $100), and probably a good investment for the future, but there's no guarantee it will work. You must be able to "mount" the disk image by double-clicking the sparse bundle for these apps to be able to see and repair it.
If you decide to do this, be sure to use only a version that's compatible with the version of OSX on your system. (If you're not sure what version of OSX you're using, see What Version of OSX do I have?)
One Last Option:
If you're comfortable with Terminal and UNIX, the procedure in this post might be worth a try: http://blog.jthon.com/?p=31 It was written several years ago, and may or may not work in your situation, especially on later versions of OSX.
If you're out of options:
You might be able to recover some of the data, but it’s "iffy" and expensive. See Data Recovery for the gory details.
Otherwise, all you can do is to erase the disk. If there's other stuff there, (not a good idea - see Time Machine FAQ #3), copy it off temporarily. Click the Erase tab, then the Security Options button, then Fastest (Lion) or Zero Out Disk (earlier). That will take a long time, but if it fails, you know the disk itself has failed. If it succeeds, the disk may be ok.