This might also be caused if you try to verify a method which expects primitive arguments with any():
For example, if our method has this signature:
method(long l, String s);
And you try to verify it like this, it will fail with aforementioned message:
verify(service).method(any(), anyString());
Change it to anyLong() and it will work:
verify(service).method(anyLong(), anyString());