Go grab AirPort & Time Machine Updates 1.0. It does what I’ve been railing Apple to fix (as well as many others)… and they have. Time Machine backups now succeed on AirPort Disk drives, connected to an AirPort Extreme base station.
Enjoy, consumer advocacy in action.
Update: There is also a corresponding firmware update for AirPort Extreme that needs to be installed. This should be picked up automatically by running AirPort Utility.
This is consistent with my prior analysis… the firmware brings AirPort Extreme in-sync with Time Capsule firmware, and the Time Machine update lets it seek out the new base stations.
I will follow up if the update improves storing on other shares (Windows, etc).