I had the same problem, using Spring 3.1.0 and Spring-security-kerberos 1.0.0.M2.
My solution was to simply copy the "new" org.springframework.security.crypto.codec.Base64
into a org.springframework.security.core.codec.Base64
inside my own application. Not super-pretty, but it works.
AFAIK, there is still no newer release of spring-security-kerberos than the 1.0.0.M2.