Hi guys, seems like I figured out my error and would like to share with everyone what I have found. Looks there are two errors. Please correct me of anything is incorrect here!
1. Zimbra LDAP doesn't use port 636. Which means of course switching to this port did not work.

I verified this with an nmap scan of my Zimbra server and this (dated) post:
LDAP/LDAPS - how to???
The post suggests to use StartTLS rather than SSL on port 389.
2. The second problem was in my understanding of the client cert. verification. The server will present its certificate when an SSL handshake is initiated, and the client chooses what do with the the cert (verify, auto-accept, etc.). I set my Perl script to accept the cert and used StartTLS and it works like a charm now! I hope this clears things up for other people as well!
Thanks,
Jake Valletta