Heavy-handed Melodyne-ing?

Yep....To get a transparent melodyne solution, you have to be very careful.
 
As you move further from the original pitch, the formants also need to change to keep it sounding as natural as possible. The further you are moving the note the more details must be adhered to in order to get acceptable results.
 
If you need to move a note one, to one and a half whole steps, you probably should record it again rather than trying to fix it with melodyne. I certainly would hit the punch in button.  You want a track that is as close to perfect as possible (pitch wise) before you start pitch correcting. That way, the moves are less then a half step and even a rushed ME job on that will often turn out totally transparent. 
 
Of course, if the singer isn't available anymore..... and this has happened to me..... I used ME to create a vocal harmony track.... and I kept the harmony vocals low in the mix so you hear the harmony but the artifacts are harder to hear.... http://soundclick.com/share.cfm?id=12024980     Melodyned harmony vox on the prechorus and chorus.
Melodyne Editor is a good tool for doing pitch correction. I have it and use it on all my vocal tracks and some instrument tracks as well. My goal is NO ARTIFACTS. If, as I'm working, I introduce an artifact, I undo and go back to the original and work with more care. I find it useful to sometimes split notes up into smaller sections and pitch correct sections individually. Slurs are also troublesome where the  singer bends a note.... and I find that is often where I get the robotic auto tuned or un-natural sound. 
 
Also... NEVER use the automatic mode. If the track is worth pitch correcting, it's worth taking the time to do it manually. Manual takes longer but yields better results.