Not sure if anyone else had this issue, but I noticed my update check was not actually checking (last check was at install time!) so I did a little investigating.
It seems that it is either looking for them in the wrong place (they are in /opt/zimbra/bin/), or missing some symlinks. To fix it, I just created 2 symlinks.
[zimbra@zimbra root]$ /opt/zimbra/libexec/zmcheckversion
/opt/zimbra/libexec/zmcheckversion: line 9: /opt/zimbra/libexec/zmjavaext: No such file or directory
/opt/zimbra/libexec/zmcheckversion: line 9: exec: /opt/zimbra/libexec/zmjavaext: cannot execute: No such file or directory
I hope this saves someone else some headaches.
ln -s /opt/zimbra/bin/zmjavaext /opt/zimbra/libexec/zmjavaext
ln -s /opt/zimbra/bin/zmshutil /opt/zimbra/libexec/zmshutil
Release 6.0.3_GA_1915.RHEL5_64_20091118095806 CentOS5_64 FOSS edition.