... you need to to grant the appropriate rights to use Personas in the COS too.
Also there is a setting to allow any from address for users:
Code:
zmprov mc default zimbraAllowAnyFromAddress TRUE
"default" may be your Class of Service. This can be set via Admin GUI too.