Qual sistema operacional você está usando?
No Centos Redhat 5. Consegui reiniciar o atd com o /etc/init.d/atd restart. Meus trabalhos em execução não foram afetados e meus trabalhos agendados sobreviveram à reinicialização:
$ date
Mon Dec 12 16:41:07 GMT 2011
Como root:
# /etc/init.d/atd restart
Eles ainda estão no atq:
$ atq
2 2011-12-12 16:37 = bobby
1 2011-12-12 16:36 = bobby
4 2011-12-12 17:00 a bobby