kinit: Cannot contact any KDC for requested realm while getting initial credentials

If you get this error message while you try to change your Kerberos password and your running server system is virtualized, you may have an entropy shortage issue which will lead to a timeout.
Linux operating systems serve random numbers using special files, /dev/random and /dev/urandom. The pool of random bits of these files will exhaust very fast in virtualized systems without hardware entropy from keyboard, mouse or actuality hardware entropy generators.
One possible solution is to install the haveged entropy deamon. This daemon will provide you with unpredictable random numbers.

For ubuntu or debian: use the following command to install the daemon.

apt-get install haveged

After the daemon is running you can issue the kinit command again. To get some more debug information write it to stdout with KRB5_TRACE=/dev/stdout in front of kinit.

KRB5_TRACE=/dev/stdout kinit username