I spent many years writing PostScrpt drivers and controllers on larger printers, but very little with EPS. One of the concepts of EPS is that it must be self-contained, which is where this is failing.
As an example in where PostScript can have issues due to not being self-contained, and for which EPS was designed to get around this, would be the case of printing out of order. If regular PostScript has definitions of fonts, their glyphs, or character encodings change, then printing out of order will possibly miss the change in one of those and end up using the previous (incorrect) encoding, glyph, font, so on (the change in state relative to font handling is inherited as printing increments from one page to the next...each individual page does not necessarily contain the full information).
A second example is that PostScript can be "optimized for size". In that case definitions of fonts and their glyphs are introduced only at the start of each page which uses them. A regular document would normally introduce the entire character set and not pieces of a character set. Printing this out of order would result in missing graphics for characters not yet introduced.
EPS is designed to be more or less copy and paste (it is an encapsulated block of PostScript, with a few rules about what it must or must not contain), but it has a weakness in that people often assume that although the structure is syntactically correct, that the data is also complete. This results in valid EPS which cannot be printed correctly. In this case you have to either add the missing information into the EPS, or else substitute. This latter is why ghostscript works, but it warns about the missing character set. Ghostscript displays because ghostscript did a substitution. Mathematica fails because it is importing an image which it refuses to do substitution on.
What Mathematica exported is syntactically correct. What Mathematica exported is where the real fault exists. Mathematica could substitute as a "workaround", but it would have been better if it had embedded the information in the first place. If Mathematica has no concept of substitution, then this is a weak point in Mathematica's import mechanism.
Normally an operating system has an environment, and if done correctly, that environment lists the current encoding. This is where the EPS information should come from if it isn't explicitly set by the user in a preference. Either the mechanism to do so broke, or else the mechanism was never run.