\usepackage{epsf}
\usepackage{psfrag}
must appear in that order, and in LaTeX 2.09 epsf must appear before psfrag in the \documentstyle[...,epsf,psfrag,...] command.
Note that the figures will not look correct in xdvi; there will be a vertical list of symbols entitled ``Psfrag Replacements'' next to them. You will have to run dvips on the file and look at it with ghostview or print it out to see how it will look in its final form.
There appears to be some trouble with centering which I have not yet tracked down. This can be fixed by replacing \epsfbox commands by \includegraphics (and loading the graphicx package at the beginning of your file) or by latexing the file on one of the Linux machines.