Actually, that doesn't seem to be solving it on Travis, although it works locally. Pegging the Shoulda Matchers gem to 1.5.1 got a passing build:

https://travis-ci.org/thoughtbot/clearance/builds/5647786

That conflicts with the reports in https://github.com/thoughtbot/shoulda-matchers/issues/259, though.