Ok, I was able to reproduce this in an edgy chroot.
It seems to be an issue with recommended packages, because:
$ LC_ALL=C sudo aptitude install kile
produces the same output as you, whereas
$ LC_ALL=C sudo aptitude --without-recommends install kile
works.
Besides,
$ LC_ALL=C sudo apt-get install kile
works too.
But I don't know which package is causing this ^^".
Ok, I was able to reproduce this in an edgy chroot.
It seems to be an issue with recommended packages, because: recommends install kile
$ LC_ALL=C sudo aptitude install kile
produces the same output as you, whereas
$ LC_ALL=C sudo aptitude --without-
works.
Besides,
$ LC_ALL=C sudo apt-get install kile
works too.
But I don't know which package is causing this ^^".