I found out by some googling(shame this became a verb! Forestling should become one...) that the reason is that the kubuntu-ppa might contain older packages than kubuntu backports, so the solution was to just disable all source which were no kubuntu archives.
For upgrading just add
deb http://ppa.launchpad.net/kubuntu-ppa/backports/ubuntu lucid main
deb-src http://ppa.launchpad.net/kubuntu-ppa/backports/ubuntu lucid main
into /etc/apt/sources.list.d/kubuntu-backports-ppa using your favourite editor or KPackageKit and run sudo update apt-get update (KPackageKit does that for you automatically).
If you are lucky you just have to run
sudo apt-get update
sudo apt-get dist-upgrade
If this does not work for you, just try alternating those two, eventually with the -f parameter until everything is installed and then reboot.
I discovered today that the ibus package wasn't installed, too so I installed it and run ibus-setup. We will see what that brings :)
KDE SC 4.5 runs a bit smoother, but sometimes it consumes peaks of 20% of the 1.8 GHz CPU of my T42p (which is still a good laptop :) ).