apt-get install msttcorefonts
О, знайшов: http://www.hanskalabs.net/node/44
А X.org перезавантажили?
http://en.wikipedia.org/wiki/Help:Multilingual_support_%28East_Asian%29#Debian-based_GNU.2FLinux