Hopefully the following will help some folks with this frustrating issue.
I’m currently running OS 10.5.8, but what I’m about to say may apply also to later operating systems.
I normally do backups once a day (I’ve set up my system with a third-party app so it does that) on my iMac. For a long time I was frequently getting the backup “Failed” message in the System Preferences Time Machine window or noticed the backup was stuck in progress or in the “stopping” mode. These problems were happening as often as a couple of times a week and sometimes were accompanied by an error message such as “can’t locate the directory”. I’d shut down, boot up again and TM might work for one backup or maybe a few and then the problem would reoccur. Then one day I twigged on the fact that the failures were occurring not long after I had restarted my computer, sometimes during the first backup after restart and sometimes on a subsequent backup. On a hunch, I changed my shut down and restart procedure and I no longer get any failures, stuck backups or error messages. If you’re having the kind of problem I was experiencing, here’s what I suggest you try: Every time you want to shut down or do a restart, first eject the backup drive and then disconnect it from your computer. Then restart your computer and only after it is fully re-booted re-connect the backup drive. This also seems to prevent Spotlight from needing re-indexing, which I found I needed to do whenever the backup got stuck.
If you aren’t able to eject your backup drive properly because TM is stuck, first try opening TM preferences and clicking on the “x” to the right of the active scroll bar. If that doesn’t stop it within a couple of minutes, try ejecting the BU drive using the Finder window. If it says it can’t because it’s busy, wait a minute or two because it might eventually bring up another alert that lets you eject. If it can be ejected, then unplug it, restart the computer and plug it back in again AFTER the restart is completed. Then try another TM backup attempt and it may work. If that doesn’t work, the last resort is to enter the code “sudo service com.apple.metadata.mds stop” (without the quotation marks) in Terminal (Terminal is an app located in Utilities) and then press the enter key, then type in your password (don’t worry if your password doesn’t actually appear in Terminal) and press enter again. That should stop TM almost immediately, but you will then most likely have to re-index Spotlight. The normal procedure for re-indexing Spotlight may not work, so if it doesn’t then you’ll have to use Terminal (in such case, go to https://discussions.apple.com/thread/1462997?start=0&tstart=0 for the instructions).
I have a Time Capsule for a couple of months now, and since the beginning I had a lot of trouble with backups failing with the dreaded error "Backup Disk not Available". Rebooting the Time Capsule fixed the problem but only for one time backup. I finally resolved the problem by opening the AirPort Utility, selecting Disks, and changing the option "Secure Shared Disks" from "With a device password" (this was the Time Capsule password) to "With a disk password" (a new password for the disk). Now it works fine over and over and I am able to backup from two separate macs without issues. Hope this helps someone.