Quizás no fui claro, uso el programa en debian lenny (versión de
pruebas). Como puedes ver en la descripción* de los programas que
mencionas, tanto cdrecord como mkisofs no son paquetes reales, son
enlaces simbólicos a los programas wodim y genisoimage
respectivamente, que fue lo que yo hice, poner enlaces simbólicos a
dichos programas.
*http://packages.debian.org/lenny/mkisofs
*http://packages.debian.org/lenny/cdrecord