Hi Dave,
It sounds like it is just a colour compatibility issue.
When the overall colour compatibility is changed in the global settings, this does not affect any existing maps; the list of colours available for selection changes, but colours that have already been selected in a map will not be changed. Is it possible that your map used colours that had been chosen under a different scheme? Did you use transparency changes at all in your map? Transparency isn't supported on your target unit, but what should happen (if the base colours are compatible) is that you would just see solid versions of the colours you selected, not different colours althogether.
If that is not the case, then it is hard to know exactly what is going on from your description - can you post a screen-shot, or send your exported shapefiles through to our support email address?
Matt