How are you restarting it. If it is just a startup issue, restarting it once should be enough, so maybe there is another problem if sometimes it takes twice?? (although if there is a problem with the tuner, it may take tvheadend a bit longer to stop than normal, so the first restart might fail because it had not stopped yet...)
If you are starting tvheadend via sysv init, then you can do
who -r
to find out what run level you are running at and then look for an "S" entry in "/etc/rc<runnlevel>.d" for tvheadend. The "S" number is used for startup order. If the number is low, you can try changing it to something very high by doing:
cd /etc/rc5.d
rm S01tvheadend
ln -s ../init.d/tvheadend S99tvheadend