Have they even started to roll out the 40/20 or even the 5 meg upload service in AZ yet?
Yep. At least on my remote terminal, they support ADSL, ADSL2+, and VDSL2. At least one person in the neighborhood has the 40/20 service per a Qwest CSR. 5M upload is also possible if you're close enough.