I just went through this same thing on OpenBSD. In my case it was a matter of adding -lcrypto to KRB5LIBS. As Ken said, check config.log to find out what the problem is, then adjust KRB5CFLAGS and KRB5LIBS. You didn't say how you configured, but if you have a working krb5-config the easiest thing is to use the --with-krb5-conf option to configure.