You should also check the clocks on all the machines involved. Kerberos is quite finicky when the time between machines starts drifting.
quite possibly. I'm not terribly familiar with Kerberos as a protocol, but I know I've definitely seen Kerberos login misbehave in a way that caused it to take multiple minutes and then time out.