It's been a while since I dealt with this, but the base issue was with the Kerberos libraries. Simple things, like nuking ~/.ssh, didn't help.
There was one solution - basically to copy the original kerberos libraries off the install cd - but the system remained flakey. In the end, I used the shotgun approach and just reinstalled everything from scratch. As a dyed in the wool Unix user, this irks me to no end. OSX sure as **** ain't no Unix if we can't get under the hood and figure out why it's broken. Reinstalling the OS is Microsoft kind of "solution."
Anyway, the system (Intel Core Duo, 2ghz MPB) had hardware troubles to boot. Bad video card (started freezing on boot %50 of the time). Ultimately it ended up smoking it's power supply (literally let the magic smoke out).
I swapped it for a Intel 2 Core Duo version and so far things are
much better. The thing is quieter, cooler, faster, more stable (no problems so far). Sure, I've broken some things software wise, but I've been able to fix them. So far so good.