KonaB777 - Given AN's domestic services provide 50% of the AN/NZ group revenues it is essential that any name does not alienate these Australian pax. Calling a domesic Australian airline Air New Zealand is hardly going to be a popular move.
In the short term, it may be that both airlines keeps their current names but the group is renamed from Air New Zealand Limited and the plethora of sub-brands are consolidated. For example, for quite a while it has been rumored that the current Ansett regional operators, Kendall, Aeropelican and Skywest (and maybe Hazelton one day??) will be simply rebranded as Ansett Regional.
I have often thought of potential names for the combined group but have always ended up with names that sounded too Australian such as Australasian or too kiwi Aetaeroa. The only potential I have ever thought which came close was Tasman (after the Tasman Sea) but it sounds like an airlione from Tasmania.