Have you tried running K3B from the command line and seeing if it spouts out any errors? If you have the correct programmes installed, it can find them and all the read/write/execute permissions are set appropriately, then you shouldn't have any problems. Unfortunately running it by clicking on an icon in the GUI doesn't allow you to see what errors are produced.
K3B, like all other programmes, uses other programmes to do the hard work - it is just a GUI wrapper for them, if you like. You will
need cdrecord, cdrdao, and some other stuff (check out the k3b
requirements page).
Or, you could try Eclipit Roaster (ERoaster, for short).