When you try to connect from a client computer tries to a GN4 server, the error may be displayed:

To solve the problem, verify that the NTP (Network Time Protocol) server is syncing on both client and server at the same way. In case there is a proxy server in between, check that its time is also synchronized.

If the above is all correct there is another thing you can try: add the following section in the web.config just after </system.web>:

  <microsoft.web.services3>
    <security>
      <defaultTtlInSeconds value="900" />
      <timeToleranceInSeconds value="900" />
    </security>
  </microsoft.web.services3>

For more info have a look at this article http://geeknotes.wordpress.com/2007/03/21/more-wse-issues-timestamp-validation-and-clock-skew/

This is not needed anymore in the GN4 versions 2.1 or newer.