I've encountered several situations where linking against the c-client.a eventually results in missing symbols. I.e. while trying to build a working php-3.0.16 RPM, it mysteriously died when including the imap module. Leaving it out let things run fine. When I changed the .spec to compile php --with-imap (statically), httpd failed to start when failing to find the symbol gss_mech_krb5. After rebuilding imap and imap-devel from the SRPM wihout Kerberos by changing this line in the imap.spec: %define gssapi %(echo 0) installing these new RPMs and rebuilding my php RPM against these new IMAP libraries, things work fine. I'm not sure if this is a problem with krb5-lib (I'm running 1.1.1-21), how ld is configured, or how the imap-devel package was compiled.
The c-client library included in the imap-devel package is only built as a static library, and static libraries by their nature cannot be linked against other libraries in the way that shared libraries can. In this case, it prevents the linker from following c-client.a's dependency on the Kerberos 5 libraries. Unfortunately this can't be solved without including a shared version of c-client in the imap package, which is not planned. The only way around it is to, as you have, manually add the Kerberos libraries to your linker invocation.