O /usr/bin/crontab tem a permissão setgid definida?
-rwxr-sr-x 1 root crontab 32K 2008-09-28 14:07 /usr/bin/crontab*
Se não, chmod g+s (e, se necessário, chown antes )
Edit: Note que isto só se aplica ao Vixie Cron (usado pela maioria das distros); outros daemons (como dcron ) podem usar permissões diferentes ( setuid ).