The Australians broke through for their first series win in India in 35 years in winning the recent series 2-1.
Fleming, widely regarded as the most tactically-astute captain in world cricket, rates Australia tougher opponents than the world-record breaking outfit he last met under Steve Waugh three years ago.
Fleming said the world champions were set to reach a new level of dominance because they prepared "much smarter" than when Waugh led them to a nil-all Trans-Tasman series draw here in 2001.
Ahead of next week's opening Brisbane Test of a two-match series, Fleming, 31, said he was surprised by the amount of detailed planning undertaken by Aussie coach John Buchanan to unhinge Sourav Ganguly's India team.
Fleming said Australia's meticulous homework put the down payment on a "clinical" series win.
"I was a little bit alarmed at how well they had planned for it. That's not always been one of Australia's traits," Fleming said.
"Because they have been so successful, they can usually get through any situation by their natural ability.
"But to see an Australian side that's thoroughly planned, and has been planning for some time, is a little bit alarming because it may take the side to a new level.
"John (Buchanan) is always pushing the boundaries but that was an interesting sign."
Australia adopted defensive field settings to dry up the home side's runs, used leg-spinner Shane Warne as a stock bowler and batted with more patience to register a first series victory in India since 1969.
Fleming can be seen as a modern-day pioneer of off-field preparations in his own right.
In 2001, only eight months after they had produced a record 16th straight Test win, he caught the Australians off guard to nearly mastermind a shock series victory here.
The Black Caps batsmen made the home side bowl at them by leaving anything outside off-stump and Fleming pressured Australian batsmen by setting unorthodox fields to plug high-scoring areas.
New Zealand's most-capped player (87) and leading run-scorer (5,566 at 39.75) said it would be a far tougher proposition to repeat the tactical success in this month's two-Test series in Brisbane (November 18-22) and Adelaide (November 26-30).
"I think everybody now plans a lot more successfully to make players uncomfortable so the opportunity to steal the march has gone somewhat," he said.
"But there still lies opportunities to explore some pressure points which is what this New Zealand team is about."
Fleming, who missed the One-day series in Bangladesh to rest ahead of the Australian Tests, admits the losses of Shane Bond (injury), Darryl Tuffey (form) and Chris Cairns (Test retirement) have left the Black Caps bowling attack "light" on experience and pace.
But he believes all-rounder Jacob Oram can lead the way, troubling the Australian top-order with his extra bounce.
The New Zealanders arrive in Sydney on Tuesday for a four-day warmup match with New South Wales starting on Thursday after an undefeated two-Test and three-match One-day tour of Bangladesh.