Well, this is part of TL i'm planning for Aden, but it could work here:
William Abdullah Quilliam founds a cult-like thingy of Muslim converts in Britain. They gather a following for some time, reaching a few thousands. Quilliam and his people recieve a charter to settle in New Zealand.
Quilliam's charisma and romanticism lead his people in an extensive project of settlement and Islamization. The islands' entire none-Christian population (as well as a sizeable amount of it's Christian population) convert to Islam.
The Muslim settlers regard New Zealand as "New Arabia", or a second Islamic Caliphate. They create a new administrative center of their country, "New Mecca".
The New Arabians discourage any religion but Islam, but allow Christians and Jews to live their segregated lives - leading many to convert anyway. Maori tribal feuds suddenly result into fierce religious fighting, and nearly 35,000 Muslim troops are sent from India to quell down things, most of these soldiers would settle down in Muslim New Arabia.
Muslim settlers and explorers lead the way into eastern and central New Guinea. After New Arabia recieves Dominion status in 1904, they demand that western New Guinea be included in their domain. The British however, not wanting to anger the Australians (who also lay claim to it) keep the area for themselves.
Parts of the New-Arabian ruled lands in New Guinea lay within the Dutch domain, which increases tensions between the two countries. In 1913, after threatening with rebellion, the New Arabian leaders of eastern New Guinea are allowed to merge with the Dominion of New Arabia. The Dutch, infuriated, begin plotting.
During WW1, the Netherlands join Germany. Declaring a massive jihad, New Arabia 'liberates' the Islamic lands in Christian rule - Dutch Indonesia. Many local nobles die during the fighting, and all survivors are execute after they are captured. The New Arabians are ruled by the Kor'an - and by nothing else.
After the war, New Arabia fought her master (Britain) and sister (Australia) for the spoils. The British argued that it would be impossible for a single Dominion to stretch so greatly across seas, and that the naval power of the Royal Navy is prefferable to it. The New Arabians showed their rather medium-sized yet mighty fleet to prove their capabilities.
After the war, there is massive movement of population from New Arabia to old Arabia - especially Aden and Oman. The oil deposits of Indonesia make New Arabia extremely rich. In 1941, Japan declares war and invades. Japanese troops even land in New Arabia herself, but are pushed out after several months. New Arabians would argue that Britain does very little to relieve their pain. Menawhile, the Japs are experiencing their own little Vietnam in Islamist Indonesia. In 1945, as the Japanese are pushed further and further back, the New Arabians manage to reconquer their territory all the way back to Malaya, as well as sieze Hong Kong and a small territory in southern China.
The Dominion of New Arabia declares independence following Japan's surrender, but maintains a firm claim to any territories it gained during the war - including Hong Kong and Singapore. The New Arabians never let go of the 'liberated' British territories - what would lead to the Commonwealth War.
British intelligence, for some reason, come with the idea that some Nazis have fled to South Africa and Rhodesia. They conduct an agressive search for the nonexistant Nazis, leading to another Boer revolt. The Muslim State of New Arabia immidietly take the rebels' side. One thing leads to another, and New Zealend and South Africa end-up fighting a war against the rest of the Empire.
Engouh for now.