did you check 'do not write colorspace information' in the compatibility options dropdown while exporting? it falls under the "anything else funky" category I mentioned above.
edit: to clarify, writing colorspace information is funky, so make sure it's checked this time.