вы пакет ttf-mscorefonts-installer в комплекте с ubuntu-restricted-extras ставите? я с похожей ситуацией сталкивался. попробуйте еще раз в синаптике (если конечно через него) отметить ubuntu-restricted-extras и установить. он при установке как раз и качает нужный вам ttf-mscorefonts-installer. если не секрет, зачем они вам?
upd: если совсем никак, смотрите в сторону liberation fonts (заменяют times new roman, arial и courier). очень замечательные шрифты. да и родные убунтовские шрифты хорошо смотрятся)
upd2:
вот ссылка на liberation fonts, если что) качать liberation-fonts-ttf-2.00.1.tar.gz. шрифты кидаем в папку .fonts (если нету, создаем прямо в домашней папке) обратите внимание, папка .fonts- скрытая)