Lower linearity requirements means that higher efficiency (lower power consuming) amps can be used. However, the data rate will have to be cut to between 5% and 20% of the downlink data rate for this option to provide tangible power savings.
The second choice, that of lowering the output power of the handset means that the needed power from the battery is lowered. That's the good news. The bad news is that with lower signal power, then the handset needs to be closer to the base station for a good connection. In other words, the effective radius of the base station is reduced, necessitating more base stations in a given geography, which increase the operator's equipment costs.
Whether both options are acceptable to operators and customers for the next two or three years, during which time power amp manufacturers push to develop high-efficiency power amps, remains to be seen.
By the way, the power-amp problem is not unique to mobile Wimax. The OFDM-based Long-Term Evolution (LTE) standard was also faced with the same problem. However, 3GPP 'solved' the problem by deciding not to use OFDM on the uplink transmissions.
On the other hand, the IMT-Advanced 4G mobile communications standard is almost sure to use OFDM. If the power-amp problem is not solved in Wimax, then it will come back to trouble designers again in the next generation standard.