I took a look at the message, and I think it can be improved a bit:

```
DEPRECATION: expectations on private predicates is deprecated. Use a public method or send(:private_method) instead. Called from /Users/myron/code/rspec-dev/repos/rspec-expectations/lib/rspec/expectations/handler.rb:24:in `handle_matcher'.
```

* The `Called from` line is worthless, as it's an internal rspec line.  You'll need to pass `:call_site`.  I think the spec warrants updating as it's hard to get right.  In the spec you can use `__FILE__` and `__LINE__`  in the expectations so that it's not brittle and tied to a specific static line number.
* I think `expectations on private predicates` is confusing.  How about `the be_xyz matcher for private predicate methods`?
* I think the `replacement` can be improved a bit as well; "Use a public method" sounds like you expect them to already have a public method they can use instead, and `send(:private_method)` isn't clear what you mean, as you can't use `send(:private_method)` with this matcher.  Instead, I'm thinking this reads bettter:

``` ruby
:replacement => "`expect(object.send(:private_method)).to be_true` or change the method's visibility to public"
```

Thoughts?

In general, with these PRs that add deprecation warnings it would be great if you would include an example of the deprecation output in the PR message so that it's easy to see without having to check it out locally :).