You should always call the History.fireCurrentHistoryState()
at the end of your GWT onModuleLoad(). I think that should solve your problem.
The thing is that the first history event ( like when you load page.com/#xyz ) is not captured by the ValueChangeHandler, you have to "fake it" with the History.fireCurrentHistoryState()