I found the cause of this. By adding universe to my security source line (/etc/apt/sources.list), I was able to install krb5-user. Ubuntu's default sources.list states:
## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu ## team, and may not be under a free licence. Please satisfy yourself as to ## your rights to use the software. Also, please note that software in ## universe WILL NOT receive any review or updates from the Ubuntu security ## team. To me, this implies that there shouldn't be any universe updates in an edgy-security distribution. But perhaps I'm reading that wrong. -- broken dependencies with krb5 packages https://launchpad.net/bugs/88720 -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs