\documentclass{article}
\usepackage{graphicx,psfrag}

\begin{document}
  \begin{figure}
    \centering
    \psfrag{x}[c]{x-axis}
    \psfrag{yy}[c]{y-axis}
    \includegraphics[width=\linewidth]{test.eps}
    \caption{The x-axis label is correctly replaced by psfrag, but the y-axis label is not.}
  \end{figure}
\end{document}
