Hoy encontré lo mismo en Heroku:
Mongo::AuthenticationError: Failed to authenticate user 'heroku_app111' on db 'heroku_app111'.
from /home/ad/.rvm/gems/[email protected]/gems/mongo-1.11.1/lib/mongo/functional/authentication.rb:205:in `issue_authentication'
No es por este RUBY-890 error, pero porque MongoLab se actualizó a MongoDB 3.0 que usa SCRAM-SHA-1 mecanismo de autenticación de usuario de desafío-respuesta. Así que necesitaba el último controlador Ruby mongo versión que cuenta con esto. En mi caso, la última rama 1.x.
Las versiones mínimas del controlador que admiten SCRAM-SHA-1 son:
Driver Language Version
C 1.1.0
C++ 1.0.0
C# 1.10
Java 2.13
Node.js 1.4.29
Perl 0.708.0.0
PHP 1.6
Python 2.8
Motor 0.4
Ruby 1.12
Scala 2.8.0
Por supuesto, debe asegurarse de que sus credenciales estén bien :)