I know it's poor form to answer your own question but just in case this helps anyone else... It appears that the issue was I converted some PSD and other files that were originally made for printing and had the CMYK color format instead of RGB.
To find this out I used ImageMagick's Identify command and did this
Identify -verbose broken.jpg
giving
Image: broken.jpg
Format: JPEG (Joint Photographic Experts Group JFIF format)
Class: DirectClass
Geometry: 256x256+0+0
Resolution: 250x250
Print size: 1.024x1.024
Units: PixelsPerInch
Type: ColorSeparation
Endianess: Undefined
Colorspace: CMYK
Depth: 8-bit
This showed the colorspace was CMYK so a quick test of the other broken images showed they all had the same issue. To convert them again ImageMagick to the rescue and used
convert broken.jpg -colorspace RGB fixed.jpg
So it appears iOS/PC/Mac all support JPEGs that have CMYK but Android appears not to or at least not all CMYK images (As of Android 4.2)