这事如果纽西兰的移民局不给出文件就很难办

原则上，因为她是在入籍时改的名字，所以中国领事馆是可以以此人改名字时已经非中国公民为由，拒绝出具证明文件的，不过你还是可以去试着问一下，看他们能否为前中国公民出一份认证，认证你女儿的宣誓和签字属实，(这种在移民法上称做second evidence，在因为某种原因无法得到frist evidence时可以作为证据使用),当然如果纽西兰领馆愿意给做最好，因为不了解他们的policy,不知道他们有否这种服务。
其它可以作为second evidence的，还有当时帮助她办理入籍手续的纽西兰官员或法官的个人证词(即使他/她现在已经离职也没有影响，如果能找到他/她人的话)，在纽西兰的邻居，同事，同学，教过她的老师....所有知道此事的人的证词都可以，要在纽西兰当地公证，再到纽西兰驻美领馆做认证，证明当地的公证属实。