IIRC Ceylon did this. It was very cool, especially with union and intersection types. They didn't use the standard java collection interfaces though. Too bad the language didn't take off.
Scala had a separate hierarchy of collections as well IIRC (and their entire collection thing seemed like a much better design than what Java did, admittedly with years of learning from Java's mistakes)
