OK, I found some help on the wiki here. And a little help internally from a linux veteran.
It appears that either zmprov or LDAP doesn't handle the new line character. We tried octal, unicode, etc without luck. The only way it work was to set a variable with \n to break the lines and get echo to interpret the new line and feed it to zmprov
Then check it:
address="New Address line 1\nNew Suite 333"
zmprov -l modifyAccount firstname.lastname@example.org street "`echo -e $address`"
zmprov -l getAccount email@example.com | less
New Address line 1
New Suite 333