SKAZ,
Try Swift Aviation (or Swift Air) - it is a growing FBO with flight training based at Sky Harbor. Another good flight school in Phoenix is Sawyer Aviation based at Scottsdale Airport.
The flying conditions are fantastic in Arizona - but expect 3-4 hot summer months - but the rest of the year the weather is WONDERFUL!!!! Hey, with 320+ days of sunshine and calm winds per year, you can't ask for much more... Trust me, you'll love it there!
. .Cheers