This is what i have in the synaptic.
main updates nonfree kde4 games xfce4
That indicates that you are installing an old ISO. You will not be able to successfully update from anything older than 2012.08. Your best bet is to download the latest ISO (2012.12).
The latest ISO indicated on the download page for KDE is 2012.08 as of today. I was going to download 2012.12 if it existed. I just downloaded the 2012.08 ISO last week because I saw the very same problem the OP was having when I did a fresh install for a friend and I was using 2012.02 and saw the very same problem after doing the update.
I think maybe it is time for me to do a fresh install on my box because I am starting to get some unpleasant behavior on it. I have been updating this box since I built it about 4+ years ago.
You should be able to download the 2012.12 iso using KTorrent or similar using the following linkhttp://www.pclinuxos.com/forum/index.php/topic,99458.msg951880.html#msg951880
« Last Edit: December 17, 2012, 02:28:36 AM by menotu »
PCLinuxOS 32bit KDE 4.10.1; kernel-3.4.11-pclos1.bfs & 64bit 3.2.18bfs; NVidia GeForce 8400GS 1GB 310.19 driver
Sony Vaio SVE1513A4ESI Laptop, Intel Core i5, 2.6GHz, 6GB RAM, 750GB, 15.6" Intel HD Graphics 4000