It looks like there is a problem with the TEXINPUTS path.
The machine used is a regular update from 5.2 to 6.0. To
reproduce... try the following code. letter.cls will never
be found.

\documentclass[12pt]{letter}
\begin{document}
\begin{letter}
foo
\end{letter}
\end{document}