The new Melodyne may be able to (when it comes out) but its really meant for solo polyphonic instruments. For example take a guitar track and change some notes within a chord. For whole mixes I think it'll work if there are few instruments and it's not too busy, like the jazz recording they use in one of the videos. Otherwise I dont know, but we'll have to wait till it comes out.
There are programs for Karaoke which cancel out the vocals by playing around with the phase. This usually works because the vocals are *usually* in the center. You'll still hear the reverb from the vocals though. Sometimes it'll take out other instruments too, but it totally depends on how the song is mixed.
I used to use the karaoke button on my stereo all the time because it usually brings up the guitars (because they're usually panned left or right) and made it easier to learn the parts. It worked especially well on old Rush albums