For long time I've been wondering why I can't seem to burn DVDs or Blu-Rays properly using k3b in Linux (or any other graphical burning software for that matter). The problem is cdrkit (a fork of the original cdrtools).
You can get the latest version of cdrtools, which actually supports burning to Blu-Ray and also should create DVDs properly, by installing cdrecord from this PPA. You might as well also install mkisofs from there too.
Prior to finding this PPA, I had compiled cdrtools from source, which is pretty easy. That also involved installing smake, also from the cdrtools author.