Meu problema foi que a versão em ruby do meu ambiente de gema era diferente da versão em ruby do rvm.
Eu usei os comandos
gem env
which ruby
Para diagnosticar o problema. Isso me deu a versão rubi usada por gem e rvm e então usei
rvm use <ruby-version>
Para combinar as duas versões do ruby.
Eu fiz uma postagem no blog com mais detalhes: Problemas ao executar o executável a partir de uma gem instalada em rvm