1. Acceptance test at the OEM level 2. Acceptance test for each individual phone 3. Another round of testing at the carrier level.
It's that third round of testing that was always the most frustrating, as it was rarely well executed. We'd get a lot of really ticky-tack things ("bugs" in the form of "I don't think feature X should work this way"), while the big problems were rarely caught. We finally built out a rather large internal QA staff which was much more effective.
I'm not against testing, but the carriers need to adapt to the new environment. Instead of trying to catch every bug (and failing) be much quicker to push updates to the network. I'd much rather have an update every month or two, rather than wait 4 or 5 months to get a fix in.
This is one thing Apple gets right. The cadence of their updates is perfect.
Carriers get a cut of the Android Market revenue (10% of the sale), so they do have some interest in seeing you upgrade your phone. However, they also insist on exhaustively testing everything that runs on their networks (or, at least, everything you get from them), which gets expensive. I'd hope the Market revenue would be more than the testing costs, but I don't know.