I think that the "legitimacy of the US order" refers to the evidence that will be presented to the US grand jury, not the search warrant in New Zealand. The Mutual Assistance in Criminal Matters Act [1] requires that the Attorney General be satisfied that the request be related to a foreign criminal matter, but they do not have to ensure that the order would be held up in the US.
[1] http://www.legislation.govt.nz/act/public/1992/0086/latest/D...