zmprov md mydomain.com zimbraPublicServiceHostname webmail.mydomain.com
This works on 5.0.16 with or without setting a zimbraVirtualHostname.
Bug 31844 - change password ignores zimbraPublicService* was supposed to be fixed in 5.0.10 (ironical same as your profile string). I'll fire up a vm to double check if it doesn't work for you.
Also of note if you use multiple domains: Per
Bug 36224 - Hosted: Change Password Form Problems you might have to switch the field 'user' to 'user@domain.com'.