We have been covering a problem where people using networked backups for Time Machine are able to run the first few backups just fine, but then the backups start failing with an "Error 109" that claims the backup disk image could not be accessed.
In our initial look at this problem, it was clear a number of users were backing up to Airport Extreme Base Stations with attached external hard drives, which is an unsupported method of using Time Machine. We then covered a potential fix for this issue, which was to attach the backup disk image so it could be treated as a device, and then use terminal disk utility commands to repair the disk image. This has worked for some people, but not for all.
Another fix has surfaced which illustrates that for some the problem may be with how the computer is managing passwords for networked backups. If a password for the Airport Extreme Base Station or Time Capsule is recognized but and error does not allow the authentication to complete, then that could easily prevent access to the backups.
The remedy for this is to remove keychain entries that are associated with accessing the Time Machine disk attached to the Airport Extreme. Open "Keychain Access" and search for the keychain entries associated with your network backup disk. Highlight them and remove them, and then go to the Time Machine system preferences and be sure to select the desired disk for Time Machine again.
Past articles on this problem: