I also believe it's a CDN thing, because when I have the issue, if I cancel and restart the download, after 2-5 tries of that it downloads immediately on LTE. I suspect that each cancel/restart gives it a chance to select a different server to download from, eventually getting to one that works.
After reading all the posts, I'm sticking to CDN/DNS being the issue. Most companies will run a production backend (servers), with a pre-production backend offing new features (iOS 9) as pre-production having beta users on that. Some people said a week before iOS 9 came out, the issues started. Note that some people are having issues on 8.4.1 and iPhone 4S.
I'm guessing that's when Apple switched the pre-production Content Distribution Network (CDN) over to production. We reach those services through DNS. When you try to download from the App Store, stream music or use other Apple-based iCloud services, Apple's CDN will try to optimize your download by picking a server that's close to you, or not overloaded, or just round-robin it, depending on a number of configuration factors.
It seems to me, that AT&T, the Australia telecom mentioned and a few other providers DNS servers or not responding correctly to Apple's DNS Servers responses, and returning bad or cached DNS entries to unoptimized servers (far away or overloaded) and thus it's taking forever to load. The Apple CDN servers could reside within AT&T's infrastructure (CDN networks may be built that way) and that server is behaving badly (bad load, server issue, or running beyond capacity).
It's not just downloads, but starting the download, the circle spinner, also takes a while before the download begins.
Remember when MR stated Apple was building a CDN a year or so ago, I assume this is just CDN roll out pains. There are a number of networking and server engineering efforts that go into building out a robust, stable CDN. The fact that it's localized to just a few carriers points to CDN issues and not completely AT&T's fault, since the rest of the data flowing over LTE seems unfettered.
That doesn't mean it isn't an AT&T issue. AT&T could be hosting the server or their DNS infrastructure could be to blame.