Try specifying the version number and start with kdebase: apt-get install kdebase=4:3.0.4-1,
where you should replace 4:3.0.4-1 with the version number you get via apt-cache. Probably there will be some dependencies you have to care for by hand. Take a look at missing dependencies and apt-get them specifying the version numbers. I think you can simplify this by configuring apt in a more elaborate way, but I don't know how this is done exactly. --Felix
