jaredonthefly wrote:In both workflows I'm losing most of the audio
That indicates that the track is almost identical in both channels, which in turn indicates that it will probably not be possible to remove the vocals with Audacity.
On last thing that you can try in Audacity is the new "Vocal Reduction and Isolation" effect: http://manual.audacityteam.org/man/voca ... ation.html
Note that it has an "Analyze" option that will give an indication of the chances of success.
Other than that, it's down to the expensive tools like Melodyne editor by Celemony
(about $400 USD)