I had similar issues on a couple of my PCs. I followed Old-Polack's excellent instructions and got things working again. But not perfectly. On both machines, I kept having some quirky issues. Dependencies missing for certain programs (although different missing depedencies on the different computers?), some programs missing. Anyway, my systems were not broken by any means. But they just didn't "feel" right.
So I downloaded the 2012.12 ISO and did a complete reinstallation on those two PCs. Although I didn't go as far as you; I kept the current partition configuration and reformatted only the "/" partition. Then I simply recreated my user and assigned my old home directories, which survived the reinstallation completely intact.
I am *VERY* happy I did this! The 2012.12 PCLOS KDE release runs just awesome, and I haven't had a single issue since.