Cannot contact any KDC for realm

[Lars Hanke]

During boot of my system (Debian Wheezy) k5start is invoked to supply a 
ticket for accessing the AD DC by nslcd. However, during boot it fails:

k5start: error getting credentials: Cannot contact any KDC for realm 
'MY.AD.REALM'

If I restart k5start using the very same init script once the system is 
up and running everything works nicely.

On another system I neither have any issues using a similar boot stack.

What exactly does this message want to tell me, i.e. where do I start 
troubleshooting?

Thanks for your help,
  - lars.