I know this thread is a little stale by now but for the sake of posterity, I was having the same issue after rebooting my FOG server (running Ubuntu 12.04 64-bit). I found that issuing:
[CODE]sudo service tftpd-hpa stop
sudo service tftpd-hpa start[/CODE]
brought everything back to life

I also found that adding
[CODE]/bin/sleep 30 && /etc/init.d/tftpd-hpa restart[/CODE]
to rc.local didn’t help (in fact, I already had that in my rc.local), however
[CODE]/bin/sleep 30 && /etc/init.d/tftpd-hpa stop
/bin/sleep 30 && /etc/init.d/tftpd-hpa start[/CODE]
did help. Don’t know why restart didn’t (maybe my server is too quick and needs some more time before it tries to restart the service - [FONT=Consolas]/bin/sleep 60[/FONT] perhaps?)

For the record (and to help anyone who doesn’t really understand Linux very well), my /etc/rc.local file contents are as follows:
[CODE]#!/bin/sh -e

rc.local This script is executed at the end of each multiuser runlevel. Make sure that the script will “exit 0” on success or any other value on error. In order to enable or disable this script just change the execution bits. By default this script does nothing.

/bin/sleep 30 && /etc/init.d/tftpd-hpa stop
/bin/sleep 30 && /etc/init.d/tftpd-hpa start

exit 0[/CODE]