I only recently discovered psfrag (great package) and was testing it on a maple plot that I exported as eps by right-clicking on the plot and choosing export->eps. When it didn't work, I searched and found this posting, thankfully. Just to add information, I'm running Maple 10.02, Redhat EL4. The above suggestion worked for me too. It's a little less convenient than just right-clicking to export however. It does seem remarkable that the two methods produce different postscript files.