OK, solved this myself, but that was wierd.
So libkrb5support.so.0 is in krb5-libs in fedora, but _not_ in RHEL. It just isn't in there. So I luckily found this link, with a fedora 4 rmp:
ftp://rpmfind.net/linux/fedora/core/...4.1-5.i386.rpm
Don't use any later rpm version or it will have have other dependancies that are not in RHEL 4.x. This installs over the existing RHEL version fine, and does include libkrb5support.so.0 !
Once that was in place, MTA started.
THen I updated to ZCS 4.5.10, and it worked.
Then I updated to ZCS 5.0.1 and it worked- however, mail was not being received till I created a new self-signed-CERT. Mine had also expired. Search this site for the directions on creating a new CERT for ZCS. I didn't have to do the ldapmodify- I just used the cli commands to make and install a new cert and that worked for me.
5.0.1 is up on RHEL4 now and seems to be working ok. Jetty seems much faster than Tomcat now!