Thanks everyone for your help. We ended up finding the problem:
We were setting explicit IDs on our elements, so our tests can grab
them easier, in GWT this is done via:
usernameLabel.getElement().setId("consoleLoginPageUserNameInput");
This works fine for most GWT inputs, but for the SuggestBox it is
handled a bit differently:
spSelect.getElement().getElementsByTagName("input").getItem(0).setId("spSelect");
After grabbing the correct inner table, we are able to interact with
this input with Selenium just fine. Hope this helps someone.
Cheers
Pedro