Thanks @vboctor and @dclaux. You guys were correct. Using a newer "ExchangeVersion" to create the service object fixes that issue, ie: the server will now send the new state. And as @MikeN123 suggested adding the "WorkingElsewhere" string to the LegacyFreeBusyStatus enum class makes it work end-to-end. (I'll create a pull request for that). Thanks everyone!
Just updated my scripts from ews-java-api 1.3-SNAPSHOT to 2.0-SNAPSHOT. Found the correct new paths for everything, but now my scripts are failing with an assertion error (expect no headers in the dictionary yet), and I don't know why