I think I understand your feeling about this, and I think I have a similar opinion.
I have worked with Java developers who turn 50 code line class into 3 classes and 3 interfaces because it's easy to understand. And I couldn't stand it.
The thing was awfully hard to understand, almost impossible to debug and never ever needed to "switch the implementation".
On the other hand, I've also seen code where multiple objects share similar behavior and are used in one place, and could really use common sorting/processing loops if the methods would have been exposed through common interface.
So, IMHO, core objects that are likely to be used in similar scenarios usually benefit from common behavior which should be accessible through interface. But that's pretty much it, abstracting simple things because it's right, or makes it possible to switch implementations is just a way to make code messy.
Then again, I prefer longer smarter classes over explosive amount of small classes with all the lifetime management issues, and hard to see relationships, and spaghetti call graphs. So some people will disagree with me.