My locale (NL_nl) also uses 24-hour format and it works without problem on 'locale-default'. I suspect that the entry for Australia is erroneously associated with '12-hour' time format.
In my locale, the month and day are erroneously switched so I used the 'custom' setting to get my weekday-day-month notation.
I also don't know for sure if the MATE desktop is using LC_TIME as reference.
It should, however, at least follow the setting of the language selector in the control-center where also things like currency symbols etc. are defined.
EDIT: By the way, it looks like you are not the only one: