Queensland has had a "whole of government" Microsoft deal for some years now, so they have been paying software assurance on Windows + CALs + Office - this means that there were already ongoing costs. Of course, most departments don't take advantage of this and are still running Windows XP, Office 2003, etc.
The IDES project to get users onto a dedicated hosted email infrastructure was a huge failure. The main stumbling block for 365 is that it is not supported on Windows XP, which as I mentioned is still running in many sections of the government. Hopefully this solution will work out better - there is certainly a great deal of commitment from the highest level to get this solution in place.
To address some of the other points above:
@frank ly: Yes, the staff do get the personal rights for 365. They used to be able to get home media for $15 anyway, so not that different.
@many: Pipes aren't that thick in QLD, but the government departments seem to do okay. Anyway, those sites down a bit of wet string would still need to get their email from somewhere, wouldn't they?
(Anonymous because I'm involved in some of this.)