Because APNs don't work that way. There's no "standard" way of doing that. It's not like over-the-air PRL updates on CDMA2K networks. On iPhone specifically, there's only one way of pushing APNs to the phone, and that is if the carrier has a carrier profile. If they wanted to have their own official, Apple-signed carrier profile on iOS, they'd have to play by Apple's rules, which presumably means becoming a contracted iPhone reseller.
Ideally, APNs would just be another value that the SIM card could carry. But I guess since packetized data over GSM predates the SIM card standard, we're stuck with this need to program them directly into the phone.
This is also a problem with Simple Mobile (a MVNO that I'm trying out with a carrier and development unlocked AT&T Branded HTC Titan). Repeatedly, it will default to T-Mobile or AT&T APN and Cell settings, causing me to lose cell service and internet access. Oddly enough, when they've switched settings and cell/internet is supposedly down, I will get MMS messages. There is no way to set the settings correctly and lock them down from an end user perspective. It's pretty much a wash when it comes to service since there aren't enough T-Mobile towers where I'm at, and after the amount I've already paid for is up, I'm switching to Straight Talk to give them a shot.
That does suck, but if it is an AT&T-branded phone, it is less surprising (although no more acceptable) that you've encountered this problem.
If you go into an Apple retail store and buy an off-the-shelf carrier-unlocked no-brand-stickers-anywhere-on-the-device Apple iPhone 4 or 4S at full price ($450/$550), you will still run into this, which is ridiculous.
Would getting the FCC involved help? It wouldn't hurt to file a complaint. I think they've forced phone companies to enable unlocking in the past, and Apple needs their approval to sell the iPhone in this country. So they may be willing to get involved.