The problem is caused by there being no entry for the current $TERM under /usr/share/terminfo.

To fix the problem install the ncurses-term package.

If that doesn't work (there is no file for the specific $TERM), a "good enough" workaround may be to symlink a similar file.  For example, assuming $TERM is  rxvt-unicode-256color and /usr/share/terminfo/r/rxvt-unicode-256color does not exist:

1. Find out the current $TERM:
# echo $TERM
   

   rxvt-unicode-256color

2. Change to the appropriate terminfo directory (here "r" is the first letter of rxvt-unicode-256color) and look for a similarly named file:
   # cd /usr/share/terminfo/r/

   /usr/share/terminfo/r# ls

   [snip output which included rxvt-256color]

3. Create a symlink with the same name as $TERM to the similar file:
   /usr/share/terminfo/r# ln -s rxvt-256color rxvt-unicode-256color
4. Test

For a proper fix, find a terminfo file for the current $TERM's terminal type.  If it is not already compiled, the tic command can be used to compile it.