I'm the happiest when I can actually solve my own problems (well, let's just say that I'm happier
. . .).
The solution to this error dialogue box popping up was as I suspected - and that it had something to do with the PDFMaker template file being somehow "awry".
Somehow the PDFMaker.xla file (which embeds the PDF menu for Excel) got placed in the Microsoft Office\Office\Startup directory, when it should have been installed in the Microsoft Office\Office\Xlstart directory. Deleting and copying the file to the correct location solved the problem, and now the application (and the PDF Maker menu) is being executed correctly.
We can mark this one Solved.