For people experiencing problems with Time Machine giving an "Error 109" when backing up to Airport Extreme Base Stations, you may be able to get the backups working again by repairing corruption in the sparsebundle image file. While the root of this issue may ultimately be compatibilities with the connection to the AEBS, by repairing the sparsebundle you should be able to continue your backups.
Apple does not officially support Airport Extreme Base Station as a Time Machine destination, which may have to do with how the device handles external drives versus a more robust handling of the internal drives in Time Capsule devices. However, regardless of the specifics, once the sparsebundle is corrupted the computer then will have trouble accessing and mounting it, resulting in the errors.
A number of AEBS owners have been looking for a solution in a growing thread regarding the issue, and user "rsva" posted his method for solving the issue, which has worked for a couple of others. The idea is to avoid directly mounting the sparsebundle (which has failed for a number of people who tried) and instead use terminal commands to only attach the sparsebundle disk image to and correct format problems. This assigns a device ID to the bundle so it can be treated as a disk, without the system trying to read and interact with the contents of the disk. Here is an adaptation of the instructions posted on the Apple Discussion boards:
Quit all applications and turn off Time Machine.
Securely connect the backup hard drive to your Mac.
Open the "Terminal" and go to the hard drive mount point with the following command:
cd /Volumes/"BACKUP DRIVE"
In this command, "BACKUP DRIVE" is the name of your backup volume. Put it in quotes if you have spaces in the name.
Use the "hdiutil" command (disk image management utility) to attach the backup bundle (this may take a while if the image is corrupted):
hdiutil attach -nomount -readwrite -noautofsck -noverify BACKUPNAME.sparsebundle
The previous command should output some information about the attached drive, such as the following:
The device may be a different number than the one listed here (ie, disk3, or disk5), depending on how many other disks you have in your system. Find the device identifier next to "Apple_HFSX" (it should contain "s2" in the name).
Run the filesystem checking command "fsck" on the attached drive with the following command:
fsck_hfs -rfy /dev/disk4s2
This command will run a repair routine on the filesystem, and should output a number of errors if found and correct them. This may take a while, so be patient, and it may mention the drive cannot be repaired, but ignore this for now.
Open Disk Utility, and drag the sparsebundle into the window under where other drives and devices are listed (should be separated by a horizontal line). Then select it and in the "First Aid" tab click "Repair Disk".
In Disk Utility, select the backup hard drive itself (above the sparsebundle) and run the "Repair Disk" routine on this drive as well to ensure the filesystem is intact.
After these steps have been run, eject the drive and plug it back into the Airport Base Station. Then turn Time Machine back on on your Mac and try running a backup again. If everything is working, the drive should backup as usual. Keep in mind that this routine will not fix the problem occurring in the first place, but should get the drive back up and running once corruption has occurred. Because of this, you may experience this problem in the future if you continue to use an Airport Extreme Base Station as the host for your Time Machine disk.