With countless hours of debugging, I've found that installing the Geocoder Gem from HEAD
actually fixed the problem, as the Gem's Author said:
gem 'geocoder', github: 'alexreisner/geocoder'
But at the time it didn't work for me. I think my database was corrupted. I say that because I had to completely remove all DBs from my Local Machine and also Remove & Add the MongoHQ addon again to my Heroku instance as well, just to make it work (since the problem persisted on Heroku as well).
Once I did that, I just re-did rake db:mongoid:create_indexes
and everything was working perfectly.