If you are doing this kind of work for clients and you are depending on them being able to see images properly on their uncalibrated and unprofiled display, you need to arm yourself accordingly to prevent these kinds of disappointments.
Firstly, no serious attempt at good colour management should rely on Adobe Gamma for adjusting a display. If your display can make use of it, invest several hundred dollars in a calibrating/profiling/colorimeter package for fixing the behviour of your display and then disable Adobe Gamma in the your Start Menu, so at least one end of the hardware part of the process is colour-managed.
Secondly, you should convert your images to sRGB with Black Point Compensation enabled and embed this profile in the image. This way, the recipient display will have a better shot at reproducing your colour intentions about right. You do this using the Convert to Profile command in Photoshop's Edit menu.
If you don't know how to do these things, buy some materials and do some watching and/or reading, such as the Reichmann-Schewe "From Camera to Print" DVD tutorial available on this website, or the many free resources on this website and others which explain how to set-up a colour-managed workflow; as for books, Andrew Rodney's book on colour management, or Tim Grey's Colour Confidence would be very useful. But the two points I made above will most likely solve your immediate problem.