Not Quite Enough to Sell Me
In short, the new navigable interfaces are useful wherever you have in-memory cached data and you want to perform range-based queries upon keys of a map or entries of a set. However, I don't think that's a compelling enough functionality to use them. I would be more excited about the new interfaces if both sets and lists implemented them (currently, only sets implement them). I also would be a more eager navigables interface user if they featured a simple associative lookup method to fetch a map or set based on key/entry patterns.
To their credit, however, you can take advantage of algorithmic enhancements such as the added thread safe versions, the ConcurrentSkipListMap and ConcurrentSkipListSet classes. ConcurrentSkipListMap is based on an efficient Skip list data structure.