"is it possible there was a problem with the installation of the rpm?"
You can check to see if mkisofs is on your system with these two commands:
rpm -qi mkisofs
If you have not tried cdrecord yet you should also try:
rpm -qi cdrecord
Be prepared. Create a LifeBoat CD.