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.  But note that few, if any, such apps will work on a NAS.

Otherwise, your only option is to erase the backups and let Time Machine start over.

If there's nothing else on the NAS, use whatever tools are provided by the maker to erase or delete the disk, partition, share, or whatever it's called.

If there is other data on the NAS, you may be able to delete the sparse bundle via the Finder.  That will take long time.  If it's extremely slow, you might be able to do it somewhat faster, via the procedure in the blue box of  #Q5 in Using Time Machine with a Time Capsule.

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.

Use the Disk Utility app, in your Applications/Utilities folder (or type Disk Utility into the Spotlight search box in your menubar).

Backups made over a network are stored in a container called a sparse bundle disk image. 

Disk Utility can't see the NAS's internal HD directly, as it can an internal or external HD, but it may be able to see the sparse bundle.

If the sparse bundle containing your backups doesn't appear in Disk Utility's sidebar as below, open a Finder window, double-click the NAS in the sidebar, then locate the sparsebundle. If the server (NAS) isn't shown, from a Finder menubar, select Preferences > Sidebar and make sure the Connected Servers box is checked.

I can't tell you exactly what you'll

see, as it depends on how each NAS maker does things, and perhaps how you've chosen to set it up.  Here's what it looks like (in Column View) on a Time Capsule;  a NAS should be similar, but with different names, and likely with some other folders, etc., in between the NAS disk and sparse bundle(s):

If you're backing-up more than one Mac to the NAS, there will be a separate sparse bundle for each Mac (the sparsebundle suffix may not appear).  Drag the one you want from the Finder window to the lower part of Disk Utility's sidebar.  It may take several moments for it to appear.

If you can't see the sparse bundle via the Finder, you'll have to use whatever procedures or utilities are provided by the maker of the NAS.

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.)