This is usually caused by a DNS resolution problem rather than an actual NTP issue. I power up and shutdown test machines all the time so things are always changing. If the configured DNS is no longer valid then boot up time can be painfully slow. In order to speed up the process there are a couple options to speedup the DNS resolution timeout.
edit /etc/resolv.conf and add the ‘options’ lines from this sample. Adjust the timeouts to whatever you prefer. Read the resolv.conf manpage for more info.