That's tarnish (can be caused by exposure to air, sweat, or chemicals), so you need a silver polishing cloth. That will make it look good as new. The jewelry cleaner you used is probably for dirt and grease. Just be careful when you polish the silver part not to rub the cloth on the enamel -- while silver polishing cloths make silver look bright and shiny, it can ruin stones and finishes on other materials.