You might also try the latest Berkshelf and solve gems which contain some fixes, e.g.:
Gemfile:
gem 'berkshelf', git: 'git@github.com:berkshelf/berkshelf.git'
gem 'solve', git: 'git@github.com:berkshelf/solve.git'
If you did that, you could try forcing Berkshelf to use the ruby resolver in your Berksfile:
solver :ruby, :required
That might give you some additional clues. But otherwise, not sure how to suggest you debug the gecode solver, and it sounds like you can’t give us an example since they’re internal cookbooks.