Here's my approach (never tried the Melodyne thing):
 
Find a tempo that's close; set your default tempo to this.
Record your track(s)
Set your snap to transients only
Snap on the downbeat of each measure in the guitar track, and use "Set/Measure/Beat at Now" to define the measure numbers and tempo map.
Do similar for other beats depending on your song. THis can be tedious, but use the keyboard shortcut (Shift-M) and it goes a lot faster.
Even if it's just guitar and vocal, using tempo-based effects like delay will work better as they will follow the tempo map.
I've even managed to add other tracks like MIDI drums, bass, and piano and quantize to the new beats - works great.
 
Neel

Just watched the video with Criag demonstrating the tempo map by dragging the clip to the ruler. Neat, but it didn't work well. After you clicked to measure 16, the downbeats of the guitar were lining up with beat 4 of each measure, so you had the snare hitting on the downbeat. Maybe the "drag to ruler" thing works for small variations, but doesn't seem trustworthy for anything else. In any case, sometimes it can take longer to fix an automated tempo map then to define it for yourself so you ensure it's right.

My experience as well. Cool trick-when and if it works.