I believe that it has to do with how "complex" the marker symbol is. In your MXD, use the symbol properties menu to display the marker symbol. From there, you will see how many layers actually make up the symbol. I recall seeing somewhere in the ESRI documentation that any "multi-layer" symbols will be "converted" to a image marker symbol therefore, some symbols will not display correctly once they are rendered as an image. I will look around some more and see if I can find the help documentation and add that link to the post.
I do have another question. When you were publishing the service from your MXD did you not get a "warning" indicating that you are using "complex" symbols .. and that they will be converted (or something like that)? Confirm this by using the analyze button from the "publish as service" button.
