Comment 23 for bug 615902

Similar to what Aggry said I managed to successfully upgrade to KDE 4.5 using apt-get -f dist-upgrade 3 times.
The process was interrupted twice due to problems with some of the packages mentioned in the comments above/
Issuing the following commands did the job for me:

sudo apt-get -f dist-upgrade ("155 upgraded, 86 newly installed, 14 to remove and 0 not upgraded" in my case; everything downloaded but while unpacking at some moment an error interrupted the process)
sudo apt-get -f dist-upgrade (the process continued and after a while another error ocurred)
sudo apt-get -f dist-upgrade (the process continued, asked about updating the file /etc/kde4/kdm/kdmrc in the middle, and then finished without errors)
sudo reboot