This has been discussed with the maintainer (#198257, #226271, #242676, #264635, #271636, #273184). The current aptitude is unable to handle UTF-8 encodings, and I produced a patch for it to fallback to "C" locale when a UTF-8 locale is detected. I prefer a tool working prorerly in english, than a localized one that's not working. The maintainer uploaded the new version with the patch included, but he uploaded to unstable, instead of t-p-u.
Please consider moving the package to testing. Thanks Konstantinos