You need to get the contacts into a contact group which is synced with Zimbra. Do you have separate "local" contacts and Exchange contacts?
I don't have "local" contacts on my i-device so I can't test.
Back in the days of iOS 2, you couldn't have separate local & Exchange contacts, so people had workarounds like
iPhone Contact Sync/Merge. Maybe that will suggest a solution.