Recently I have been facing some issues with locales in Debian and Ubuntu based Xen based virtual servers. These typically appear while running the man command and apt-get or dpkg commands.