I wonder how my install differed from yours.
I literally have a bunch of programs memorized that I use and I just sit at terminal after a fresh install and knock them down one at a time.
sudo apt-get install k3b
sudo apt-get install audacity
sudo apt-get install amarok
sudo apt-get install vlc
on and on...
Man...
Well if you ever get back to Ubuntu and you tinker with k3b again and get it working, post back here. I'm curious to know what was up with that.