<p>What Abstract Datatypes should be added to OpenJDK7 ?</p>

If you look at these two links you will see what some people feel is missing:
http://commons.apache.org/collections/
http://code.google.com/p/google-collections/
My favourite missing one is Bag... it is easy to implement, but annoying to have to implement it.
Mulimaps would also nice to have in the standard packages.