The challenge is, with a PoD no earlier than 1 January 1601, have an Australian continent featuring at least 5 distinct countries/territories. Bonus points if one country is an independent Aboriginal nation.
One idea I've always had for Balkanisation was for the Dutch to colonise Western Australia before Cook first checked out Botany Bay in 1770. This might spark a sort of colonisation race for Australia, much like the Scramble for Africa (albeit not as rapidly as the SfA).