A friend had the same problem:
apt-get remove passenger
gave "passenger is not installed"gem uninstall passenger
gave "passenger is not installed"passenger -v
shows it is installed
The reason is that she had installed passenger with Ruby 1.9.1 and since upgraded to Ruby 2.1.5. (note: rvm was not installed).
The answer is to gem1.9.1 uninstall passenger
which prompts if you want to remove the gem and packages or just the gem.