I've managed to solve this problem. Basically I've created a class extending the HashMap:
public class MapStatusChanges extends HashMap<WFStatus, Pair<WFPhase, ArrayList<Pair<AppUser, Date>>>> {
...
}
And then created a CustomSerializer to the MapStatusChanges.
It's not a generic solution, but it works until this problem is solved at GWT.
Hope this helps....