I'm pretty sure this is a bug which was fixed in krb5 1.9.2 (see issue 
#6952).  You may be able to convince Ubuntu to backport the fix to their 
package, or upgrade their package to 1.9.3, although with 12.04 out I 
don't know how easy that will be.  I apologize for the inconvenience; it 
was a small typo on my part which broke a whole category of cross-realm 
scenarios.  We now have automated cross-realm tests which would catch a 
bug like this.