Верстаю курсовую с помощью LaTeX. Возникло желание использовать шрифт
Times вместо обычного Computer Modern.

Написал в преамбуле

\usepackage{times}

но никаких изменений в тексте нет. В процессе трансляции latex выдает на экран следующее:

LaTeX Font Warning: Font shape `T2A/ptm/m/n' undefined
(Font)              using `T2A/cmr/m/n' instead on input line 9.

С учетом того, что times.sty всего лишь переопределяет шрифты (\renewcommand{\rmdefault}{ptm})
можно сказать, что latex не может найти нужный шрифт.

Как сделать так, чтобы он его нашел?

Дистрибутив - Debian Etch
-> dpkg -l | grep texlive | cut -d " " -f 3
texlive-base
texlive-base-bin
texlive-common
texlive-doc-base
texlive-font-utils
texlive-fonts-extra
texlive-fonts-recommended
texlive-lang-cyrillic
texlive-latex-base
texlive-latex-extra
texlive-pdfetex
texlive-pictures