It hasn't been a long time that the kids are in NYC, but in teenage time it seems forever to them. Teenagers can be very resilient, but change of this type(moving a long distance to a very different environment) can be difficult to deal with on top of all the other things that teenagers deal with. One thing I would check into is how school is for them- are they having social issues at school, such as being treated like outsiders, not being considered 'cool' enough, etc. That may be fueling their desire to go back to AZ.
Counseling may also help, as sometimes a third party without any stake may be able to clarify what's bugging whom and suggest ways to work it out. I'm not all that sure that moving them back to AZ will resolve everything for them in the way that they wish. That's my $0.02, and I hope things work out OK for all.