The 1999 vote wasn't to leave the Commonwealth, it was an explicit referendum on whether Australia should become a republic (and it would remain part of the commonwealth). Australia is a 'Commonwealth' in itself. Australia's movement away as a reaction of the monarch's use of power in 1975 was the 1984 Australia act where the references to the UK were removed from the constitution (Queen of the UK -> Queen of Australia).
It's hard to argue using the popularity argument. In Britain, Canada, Australia and New Zealand the monarch is near universally popular.
The argument for a sovereign head of state is a complex one, the Queen isn't considered as an ordinary family inheriting a lot, its a family which is essentially the head of state and the 'inheritance' goes towards running the country and the benefit of all.
I would understand the disdain from an American perspective, but there's a lot more to it than what is conveyed - the constitutional monarchy system of today isn't like the one 300 years ago, its a wonderful system - to many better than the US system of government, admittedly myself included (I'm an American Politics major if you think there's any bias).
Keep in mind the monarch is there by choice - through democratic vote. As for Australia the 1999 referendum wasn't the first one of its sort either.