das hängt warscheinlich schon mit der Installation zusammen. Mit Java hat das nichts zu tun nur mit den Abhängigkeiten, da zusätzliche Pakete entfernt oder aktualisiert wurden.
Dann kommt es mit schlecht gewarteten experimentellen Paketen mit unter zu Inkompatibilitäten.
Es liegt warscheinlich an "cdrecord" mit dem k3b arbeitet. Ich würde erstmal cdrecord deinstallieren, neu installieren. Wenns das nichts bringt: cdrecord deinstallieren, das Sourcepaket besorgen und von Hand übersetzen und installieren.
Aber immer schauen, was beim (De)Installieren vom System ggf.zusätzlich entfernt oder installiert werden soll.
Nützlich wäre die Information, welche Linux Distribution Du benutzt.
Gruß, zagadka