This looks normal. You had a buggy version of kdelibs, and an upgrade fixed it.So, since 4:3.5.5a.dfsg.1-1 is now in testing, it's now solved as far as I'm concerned. Puzzling, though.
If anyone else than Ulf Leichsenring still experiences this issue in testing, please report.
For reference, this is upstream #135561.