I was seeing the same symptoms, and did a little bit of research onto it. Got it to work by switching gecode versions:
brew switch gecode 3.7.3
Then uninstalled the offending gems:
gem uninstall berkshelf
gem uninstall solve
gem uninstall dep_selector
And finally reinstalling bershelf:
gem install berkshelf