This week's book giveaway is in the OCAJP forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide 1Z0-808 and have Jeanne Boyarsky & Scott Selikoff on-line! See this thread for details.
The difference is that Collection is an interface, but String is a concrete class. When the compiler sees (b instanceof Collection), it knows that the declared type of b is TreeMap, which does not implement Collection. But (as far as the compiler knows) b may actually be an instance of some subclass of TreeMap which does implement Collection. I don't want to imagine what sort of poorly-conceived design such a class would have, but it's theoretically possible. A subclass of TreeMap could implement any interface as far as the compiler is concerned (though some may be impossible due to method naming collisions, but the compiler isn't going to analyze that particular point here).
On the other hand when the compiler sees (b instanceof String), it knows b is a TreeMap, and that no subclass of TreeMap could ever possibly be a String. They are unrelated types. (Plus String is final.) So the compiler flags this line as an error.