Well the only thing I advised was to set PS to use the Adobe colour space.
The reason for this is that it is a wider space which includes both RGB and CMYK.
None of the images you have posted so far have an 'embedded' profile, and, as the screenshots you provided don't contain this information, (hence my prompt to show the INFO Panel), I'm guessing this is still the case.
Therefore, they will still show as a mis-match and you'll get the '#' symbol AND the profile of (untagged).....see your INFO panel.
You can 'assign' or 'convert' an image profile regardless of it having one already, see this link for a good explanation.
http://www.peachpit.com/articles/article.aspx?p=1315593&seqNum=6
You can do either of these from the same menu, EDIT > Assign or EDIT > Convert
If you save your image via 'Save For Web...', (and you always should for web graphics), the dialog box defaults to saving with an sRGB profile.....there is a checkbox to turn this on or off....leave it on.
Using 'Save As...' saves the image with whatever profile it has.....so if it doesn't have one, as in your case, then it doesn't get one.....hence why it looks different in 'Paint'...it still has no profile.
Give the image a profile or save it via 'Save For Web...' with sRGB checked and you'll start to see things be a little more consistent across programs and browsers.
Regards.
MrToM.
