One of my startup scripts (for sphinx) returned the following message on every startup on my XEN based VPS which prevented sphinx from ever starting on bootup:
sudo: sorry, you must have a tty to run sudo
To fix this issue, edit /etc/sudoers (using visudo) and edit out
Defaults requiretty