Well, I saw a lot of other threads in these forums that helped me, so I figure I'll give back. Here is what I needed to do:

Migrate from old server running CentOS 4.4 on 32-bit to a new server running CentOS 5 on 64-bit. Change server name, since we needed to bring up the new server completely on it's own and be tested before the switch. Then, upgrade from 4.5.9 to 5.0.8 Admittedly, I somehow missed the note that I should have upgraded from 4.5.9 to 4.5.11 before the 5.0.8 jump. But for the most part, it works.

Here are some of the docs / posts I based my process on (Many thanks to John Holder and some of his posts, but his process made this fail the first time in test):
Network Edition: Moving from 32-bit to 64-bit Server - Zimbra :: Wiki

Here is the process
- newserver: Install ZCS 4.5.9 64-bit as a fresh new install. Use the new server name, but make sure the domain name and all other options are set exactly the same (including LDAP password)
- From the localconfig.xml on oldserver, copy the zimbra_mysql_password and the mysql_root_password values into the same file on newserver
- newserver: Delete everything under /opt/zimbra/openldap-data
- Copy over /opt/zimbra/openldap-data/DB_CONFIG from oldserver to newserver
- oldserver:
su - zimbra; openldap/sbin/slapcat -f /opt/zimbra/conf/slapd.conf -b'' -l /tmp/migrate_ldap.ldif
--- At this point shut down Zimbra on the old server, but leave the OS up.
- Copy migrate_ldap.ldif from oldserver to newserver
- newserver: s
u - zimbra; openldap/sbin/slapadd -f /opt/zimbra/conf/slapd.conf -l /tmp/migrate_ldap.ldif
- newserver: Confirm data load by running
openldap/bin/slapcat -f /opt/zimbra/conf/slapd.conf
--- At this point the data needs to be moved over. To save having to heavy-lift the data twice, I created a temporary directory under /opt/zimbra to move everything to and moved the data into the correct directories. The command I used to move the data was: (oldserver):
dump 0 -b 64 -f - /opt/zimbra | ssh root@newserver "(cd /opt/zimbra/transfer; restore -x -b 64 -a -f -)"
- newserver: Replace (delete current and move original into place) the following directories:
-- /opt/zimbra/store
-- /opt/zimbra/index
-- /opt/zimbra/db/data
- newserver: Remove any backup sessions by running: rm -rf /opt/zimbra/redolog/*
- newserver: replace any custom skins.
- newserver: Make a backup copy of the current /opt/zimbra/conf/localconfig.xml
- newserver: Edit /opt/zimbra/conf/localconfig.xml and replace all instances of newserver name with oldserver name to make the rename function work correctly.
- newserver: As the zimbra user, run /opt/zimbra/libexec/zmsetservername newserver-name
- newserver: Start the new server with the old version with: zmcontrol start
- newserver: After all the processes have finished, check everything with: zmcontrol status
- newserver: Login to the administrative console and verify that everything is there. You will get a self-signed certificate error, which is expected since the official certificate was not copied (yet).
- newserver: Login as a user and verify that mail, calendar, etc. are correct.

Now everything will be up and running on the new platform with the new name. Upgrade time.

One big note I found post-upgrade: There is a 'feature' introduced sometime around 5.0.6 that makes everything very sensitive to SSL certificates not matching the physical server name. In out environment we always use unique names for the servers, the CNAME to the name we want people to use. (i.e. mail.mydomain.foo versus mailserv02a.mydomain.foo) Therefore the SSL certificate name didn't match the server name once I installed the commercial certificate. See Bug 29600 – provide a configurable way to allow mismatched certificate for java to LDAP starttls for more information. Long and short, run
zmlocalconfig -e ssl_allow_mismatched_certs=TRUE