This happened to me with Vagrant, but the issue isn't specific to that gem.
I was using an older version of Vagrant which was installed via a gem which provided a binary. I was using rbenv. The Vagrant maintainer depreciated the gem and provided an installer. I uninstalled all my Vagrant gems and ran the installer. Then this happened:
jd at James in ~ ><((°> vagrant --version rbenv: vagrant: command not found jd at James in ~  ><((ˣ> echo $PATH /usr/local/share/npm/bin /usr/local/share/python /usr/local/bin /Users/jd/.rbenv/shims /Users/jd/bin /usr/bin /bin /usr/sbin /sbin jd at James in ~ ><((°> /usr/bin/vagrant --version Vagrant version 1.1.5
What's going on?!
It turns out that rbenv installs shims for all binaries, which auto-switch to the appropriate ruby version before invoking the real binary. To fix all that mess, run the following:
Definitely rather surprising. Postmodern (who resolved this issue for me) suggested chruby as a potential solution you never want to think about this again.