If you have problems with Illustrator and PSfrag, that’s probably because you can’t have psfrag replace tags with more than one character, once you saved the EPS with Illustrator. I think I found the solution, at least using CS5, and if the file is not too complicated. When saving the EPS, choose for Version the Illustrator 3 EPS. In this way you’ll be able to replace tags with more than one character.