By and large new uninhabited landmasses were discovered in one of three ways:
- By hunter-gatherers, walking there when the sea level was much lower at the end of the last glaciation.
- By hunter-gatherers hopping there from nearby islands or landmasses using their small coastal craft.
- By farming people with ocean-going vessels (usually Austronesians).
So let's look at #1. Here's what the coastlines looked like at the end of the last glaciation:
Notice that while Australia is still not connected to Eurasia, it comes damn close. Also (if you squint a bit) there are all sorts of convenient island chains in between the two.
Also notice that the distance between Madagascar and Mozambique is almost unchanged, as is the distance from Australia to New Zealand, and those distances are far greater.
The navigation techniques employed by hunter-gatherers are generally not designed to work far out of sight of land. A boat that is good for coastal fishing and/or transport is a far cry from something one could entrust their life to in the open ocean. Ocean navigation itself requires a whole suite of specialized techniques (including math) that really can't be developed in societies lacking the stratification and specialization afforded to farming societies.
So given that the distance to the horizon is about 5KM (3 miles), in the absence of convenient mountains, any body more that about 10KM from the coast is going to take some luck to bump into. The further off, the more luck needed.
Madagascar is 419km across the Mozambique channel at its closest point. Even if Mount Everest happened to be on the other side of that channel, it would not be visible to a sailor within sight of the African side.
New Zealand is ten times that distance from Australia. There's pretty much no way a breeding colony of humans is going to just randomly bump into that.
So this means both landmasses were in wait of a farming society to discover them. Enter the Austronesians. They had a agricultural package of domesticated crops and livestock that allowed for job specialization, and used it to create a specialized class/guild of navigators in their society. These folks developed and passed on the open-ocean sailing techniques that allowed their society to discover and populate a third of the globe.
Of course discoveries of nearby islands brought the opportunity for more discoveries, so this process took some time to finish populating the entire Pacific. New Zealand wasn't hit upon until about the 13th Century.
Native Australians of course were physically closer (but still not close!). However, being hunter-gatherers, they simply did not have the means to bridge that gap.
Now, how about Madagascar, you might ask? After all, there were farmers in Africa pretty much as early as there were farmers anywhere on earth! Shouldn't it have been discovered earlier by African farmers, and not had to wait for Austronesians to find it?
The problem there was the initial farming package in North Africa was temperate climate crops. These don't grow very well south of the Sahara. A different tropical crop package was developed there, relying on millet and sorghum. This didn't happen until about 2000 BC directly south of the Sahara in West Africa, and it took a large amount of time for these farmers to displace the hunter gatherers in their march across the continent, and then south. They didn't reach Mozambique until 1-2,000 years ago, and by then the Austronesians were either already living in Madagascar, or nearly there.