I like to describe Java interfaces as "multiple inheritance from abstract base classes that live in a secondary type system." Here are four drawbacks:
They're a secondary type system completely separate from the primary type system in declaration and use. Is your object a foo or does it merely implement a foo? Why should there be a distinction?
They don't provide any code (unless you want to talk about constants defined in interfaces, for which Java's rules have always confused me).
You can't add them after the fact to a class without editing its source code and recompiling. This probably springs from the first problem. (If they'd solved the first problem, you wouldn't need to do this!)
The standard library doesn't take them seriously enough. If you're going to declare String as final, at least give me some way of providing something that works like a string that the standard library can accept. I think this is also part of the first problem above.
The first problem is the most damning from the purist's perspective. Java's designers recognized a real problem (a single-rooted inheritance scheme is inadequate to express real solutions), but they created a secondary type system and didn't take it seriously.
From a practical perspective, the second problem is worse. The designers recognized that a single-rooted inheritance scheme is inadequate to express complex behaviors of real problems, but they completely failed to allow for any code reuse! "Objects that implement this interface all behave similarly, but multiple inheritance is bad so you'll have to copy and paste code to make it work."
I agree that most problems with interfaces derive from the multiple inheritance workarounds rather than the interfaces themselves. But from a non-purist perspective they're generally quite nice to work with, particularly when you're designing a large system. And using copy-and-paste instead of MI is IME never an actual problem because you can either define it in a common base class or move it to another class and use composition.
I also agree that for most of the standard library interfaces are not used enough. There are exceptions (collections, io) but they prove the rule.
As a workaround (to a workaround I guess) there's a good deal of activity around different AOP solutions to implement mixins, even applying them to compiled classes. The only problem with this is the typical problem with AOP -- you don't know by looking at the implementation what it can do or how it can be used, you've got to have knowledge from somewhere else (configuration files or other classes). Or you have to rely on an IDE to do it for you, and then you're tied to a particular tool, which may be even worse.