To the extent that the airline is enforcing immigrations laws, it is likely doing so at the direction of a government official or government regulations, or sometimes as an actual agent of the government.
Essentially, in the first instance, the airline would have an illegality defense to a claim for breach of contract. An airline can't be found to have breached a contract if doing so would require it to do something illegal, and the airline would take the position that it has been asked to do something illegal, even if it is not particularly nefarious if it interprets relevant government regulations as prohibiting the proposed travel.
In the second instance, the government for whom the airline was acting as an agent might have liability, but the airline, as a disclosed agent, would not have liability for acts it was directed to carry out by the principal who would be the government. And, while the government itself might not be immune from liability in New Zealand, the government would probably be entitled to some deference when interpreting its own regulations of international commercial air traffic in a context that is likely to present an issue of first impression as far as case law is concerned. I also strongly suspect that the government (indeed, for that matter, the governments of A, and B, and C simultaneously) would be entitled to intervene in the civil case to express its opinion on the meaning of the relevant regulations to similar effect, even if the illegality defense, rather than an agency theory, were presented.
Perhaps, there would be a claim for restitution or unjust enrichment, even though the contract failed, because the airline arguably provided nothing in exchange for the fare and was unjustly enriched by taking the money and providing nothing, even though it didn't breach any contractual right. Restitution is routinely available when non-fault based grounds for rescission of a contract are present.
If the transaction could be characterized as rescission by the airline in its discretion, arguably there would be a right to get the money back, or at least, to apply the funds paid as credit towards another flight in a manner similar to the way that someone would if a flight is canceled due to weather or some similar reason, in the discretion of the airline.
As a practical matter, however, this might very well cost more to litigate and more time and effort on behalf of the customer, than the amount in controversy would justify. A successful lawsuit would easily involve $30,000+ of specialty lawyer time to litigate, might be subject to arbitration (would could cut either way), and would be a poor candidate for a class action as the facts are so esoteric.
This argument gets weaker if buried in the fine print of the contract adopted by reference in the ticket purchase there is a "no refunds under any circumstances" clause and a "customer is responsible for determining a right to travel under applicable immigration laws" disclaim of some kind in there.
The right to a refund gets stronger if the tickets were refundable or changeable.
And, if the trip was insured, there would probably be a valid travel insurance claim to get the money spent on the trip back, although one would have to carefully look at the definitions of an insured loss and of exclusions to the policy to be sure.