Phoenix at least has two Cancun flights a day which helps a little in case you miss it. All US and AA flights are within T4, there is no switching terminals. Even though international there's not any additional security or anything to go through. It's tight but I've done 40 minutes connections often.

But yes, ideally I'd say 60 minutes to give a cushion.