No seu programa, você provavelmente esqueceu de fazer o uid real e efetivo definido para o mesmo valor. Os gids também devem corresponder ao gid da raiz. Algo parecido com isto:
setuid(geteuid());
setgid(getegid());
Veja, por exemplo, sue
(um simples setuid / wrapper setgid).