Miinstrel,

Before you blame Photoshop (Not that I'm implying that PS is NOT the problem) have you tried opening the jpeg in a different program, perhaps Picassa or your browser or even opening the JPEG itself in Photoshop.

I've found funky problems with merging layers, but completely flattening the image usually causes no problems.

I'd be interested to see the actual JPEG of the map rather than a screenshot.