http://docs.oracle.com/javase/6/docs/api/java/util/Map.html
The order of a map is defined as the order in which the iterators on
the map's collection views return their elements. Some map
implementations, like the TreeMap class, make specific guarantees as
to their order; others, like the HashMap class, do not.
GWT doesn't make any alterations to Map-based classes. Map and many of its subclasses do not keep order of insertion for performance reasons. LinkedHashMap, by design, does keep its insertion order. That is, of course, assuming you're starting with a LinkedHashMap and not constructing it from another type of Map which may not actually preserve its order during the insertion, causing the LinkedHashMap to have a different order than you're expecting.
I'm wondering why you need to keep the initial order anyway, and why are you using Map if that's what you want?