Comment 1 for bug 157230

cdrecord has been replaced by wodim, although I have both cdrecord and wodim installed in Ubuntu Hardy (cdrecord from the multiverse repository).

Please look into the "Programs" settings in k3b and try the "Search" action from there: it should discover the required programs.
I guess that cdrecord has been replaced on your system with wodim, but the paths have not been adjusted.