This question is ancient, but Mockito v2.1.0+ now has a built-in feature for this.
verify(mock, description("This will print on failure")).someMethod("some arg");
More examples included from @Lambart’s comment below:
verify(mock, times(10).description("This will print if the method isn't called 10 times")).someMethod("some arg");
verify(mock, never().description("This will print if someMethod is ever called")).someMethod("some arg");
verify(mock, atLeastOnce().description("This will print if someMethod is never called with any argument")).someMethod(anyString());