Damn! Just figured out the cause. I can see why it didn't work, but I think the way it works is wrong (or at best, the terms used are ambiguous)

My "Basis of Product tax" / "Basis of shipping tax" items were set to "Store" rather than "Shipping"

There is a problem here as my tax zone definition includes all the states of Australia, so therefore when you sign up as a user in a different state, you should be considered in the same zone, (ie. the one zone containing ALL the states) and therefore the tax rate should have been applied.

I can see why this might not be considered a bug though, so I suggest the following.

Can you please change some of the places where the term "Zone" is used to something like "State/Territory"? When you configure your store you set up a Country and a Zone - which for me is a State.

Then, when you set up a zone for tax reastons, you create a zone name (which could be anything and isn't necessarily a state/territory like the last zone had to be), but that zone contains sub-zones which in turn contain zones (ie. state/territory). Having a zone containing a sub-zone containing a zone to me suggests that at least one of those "zones" should be called something else.