Why won't Time Machine work with a drive connected to an Airport Extreme?
Solution 1:
Not a complete answer, but this document might help: Time Machine Server Requirements
To be listed as a backup destination, the AFP server must advertise it with specific features and flags turned on. Airport Extreme storage doesn't show up because it's missing something from that list, but the question is what?
I found a reference to the Extreme's AFP implementation lacking some caching capabilities (link) but I have no idea if that's true. It is plausible that it doesn't have the storage required for the replay cache.
It's also plausible that it does have all these features but Apple chose simply not to enable the Time Machine flag.
Note that the newest generation (the big ones with 802.11ac) does now officially support Time Machine, so this doesn't seem to be an issue anymore. That's probably because they're now almost identical to the current Time Capsule inside.
Solution 2:
I have had this working fine, just by initialising a backup over local USB, then moving the drive to the AE, and selecting a the same drive over the network location. All worked fine.
Solution 3:
I've also heard it's unsafe, with the explanation of journaling, the "log book" for the hard drive. This journal contains the actions an operating system is "about to do", so the operating system knows what it was doing in a recovery after a write failure (for example, because of power loss). It's easy for a backup over a network share to be interrupted, for example, when the network temporarily falls away. Since a lot of caching is involved in network shares, including caching of the disk journal, you can't always be sure that the remote journal is updated, causing the physical on-disk journal to be out of sync with what the operating system thinks is in the journal.
All of this said, though, I still don't completely understand why it's not possible. Time Machine handles interruptions quite well as far as I know: until a backup is completed, it is in a separate place that doesn't confuse the software if it goes wrong. I.e. maybe the operating system can't fully recover all write problems but at least this can't mess up a backup. Only at the very end of the backup is the backup moved into place with a single, atomic operation. In my mind, the above explanation is a hint, but it isn't a complete answer...
Solution 4:
There's no technical limitation. You simply need to plug the disk into your Mac and format it as "Mac OSX Extended (Journaled)", however, it's been reported to be unreliable.
Airport Extreme + USB Drive vs Time Capsule