Mac – How Do I Target an Airport Extreme Shared Disk for Time Machine

It looks like Apple may have changed something since I last configured this…

Some time ago (maybe two years?), I bought an Airport Extreme and plugged an external hard drive into it. From my laptop it was simple to configure Time Machine to use that shared disk as the storage. It created a sparesebundle and it's been happily backing up ever since.

Now I have a new disk to use. So I removed the old one and installed the new one and prepared for that initial very large backup over the network. However, it would appear that there's no option to use this shared disk for backup purposes.

When I enter Time Machine preferences and opt to select a disk, there are no disks listed:

Even though there are actually two network drives (and the local drive) mounted:

In this case, "Backup" is the drive shared from the Airport Extreme.

If I opt to "Set Up Other Time Capsule" it takes me to the Airport Utility (6.1) in which I find no options mentioning any kind of Time Capsule setup. It lets me share or un-share the disk, that's about all I can find.

I also tried downloading Airport Utility 5.6 to see if the older interface had some familiarity for me to set up the disk for Time Machine, but again all I seem to be able to do is share or un-share it. I can't seem to tweak anything that would result in the Time Machine Preferences actually seeing the target disk.

Has anybody run into this issue before? Is there something simple that I'm overlooking? The driving factor in getting a new disk was to increase the size so that I could use the same disk for automated backups from my Linux box (which would mount the share and run some simple cron jobs using tar for incremental backups), which mounts the share just fine (the last mount point in the list):

Ultimately, how can I use a disk shared from my Airport Extreme as a storage target for Time Machine in OS X 10.7?

Edit: To add some clarity, the hard drive in question was formatted on my Mac. It was given a single partition and formatted as "Mac OS Extended (Journaled)" and is 3 TB in capacity.

I've searched around on the internet and people who are experiencing the same symptoms all seem to be using some off-the-shelf NAS. The general theme is that the firmware for each such NAS needs to be upgraded to support updated protocols. However, the controlling device in this case is an Airport Extreme which, to my knowledge, is fully up to date. So I can't imagine why anything would be unsupported in this case.

I was previously using the same setup with just a different external hard drive. That worked fine. Time Machine could mount the drive and perform the backups all by itself. All I did was swap out the drive with a new one, and now Time Machine can't use it.

I've also just noticed that when Time Machine tries to start a backup, the "Name" of the target device get appended with a number. It started with "-1" and then I tried to de-select and re-select the target disk, not it has a "-2":

Update: Just to test, I've removed the drive from the Airport Extreme and plugged it directly into my MacBook Pro, and it's currently in the process of backing up without problem. I'll try re-adding it to the Airport Extreme after and see if perhaps it can back up (maybe the problem was in the creation of the sparsebundle on the file system? it's worth testing).