> One interface per one concrete class
I vaguely remember language support for something like this in the SatherK dialect of Sather. Sather itself was inspired by Eiffel. One-interface-per-class actually is no problem if it's well supported in the language, by simply adding a single special character to the concrete class name.
It worked something like putting some sigil (dollar sign, IIRC) in front of a concrete class name meant that the code was referring to the public interface exposed by the class. (I could have gotten it backward in that maybe you needed the sigil in function signatures/field declarations if you wanted to force the concrete implementation instead of the interface. I think it evolved from the normal Sather dialect, where interface declarations looked pretty much like class declarations except that the name began with a sigil. If it hadn't evolved from standard Sather, I suspect they would have required the sigil if you really meant to intentionally restrict your code to the concrete implementation.)
Java could have headed off a lot of premature abstraction by making it easier to later replace a concrete implementation with an interface. Instead of making "new" an operator, Java should have made "new" a static method returning an instance of the class, with a bit of compiler flow analysis to allocate an object the first time you referenced "this" within "new". The chief advantage is that it would have minimized the amount of code change necessary to replace a concrete class with an interface if needed. If new is a static method, then the interface's "new" can return some reasonable default implementation, or decide among implementations at runtime.
You'd still need to recompile everything, so that all callers would use the invokeinterface bytecode instead of invokevirtual. Alternatively, invokeinterface/invokevirtual could be collapsed into one opcode, and rely on polymorphic inline caches/hot spot inlining to remove most of the method dispatch overhead. A third option would be to have the bytecode verifier perform invokevirtual/invokeinterface substitution at class load time in cases where a concrete class has been changed to an interface or vice-versa.
Making "new" static factory methods instead of an operator would also make it possible for a class to transparently swap in specialized subclass implementations (for instance, specialization for BigInteregrs that fit in 64 bits, or Strings where all codepoints are less than 256). PyPy does a small amount of this specialization internally for Python, but it would be nice to have language-level support.