Interestingly enough, Term::ReadKey works fine under Perl5.5.3 installed on this very Debian. I had a closer look at how the Debian folks compiled perl5.8.0:
usethreads=define use5005threads=undef useithreads=define usemultiplicity=define
Hell, why did they compile it with threading-support (which I neither need nor want)! I somehow suspect that Term::ReadKey doesn't work due to this.