I suggest posting your original photo to see if anyone is willing to use it as a test.
Did you try the original color version on the Kindle? I don't think making it gray scale should be necessary in general. This does give you maximum control over the result though. Also, a 600x800 image will be reduced in size (because the image display area is not the full screen). HarryT recommends 400x600 for cover images, although this won't use all of the available space.
Also, if you have a SD card Alt-Shift-G will create a screenshot on the Kindle to illustrate the problem, see
Igor's Keyboard shortcuts.