Nonce Code or Nonce Timeout

Question

My Client has a Java webservice and I am trying to consumem it using wcf .

It uses a usernametoken with nonce, createddate.. This is the link I am using http://weblog.west-wind.com/posts/2012/Nov/24/WCF-WSSecurity-and-WSE-Nonce-Authentication, Following code generates nonce. This simply appends to the string.

    string phrase = Guid.NewGuid().ToString();
            var nonce = GetSHA1String(phrase);

protected string GetSHA1String(string phrase)
    {
        SHA1CryptoServiceProvider sha1Hasher = new SHA1CryptoServiceProvider();
        byte[] hashedDataBytes = sha1Hasher.ComputeHash(Encoding.UTF8.GetBytes(phrase));
        return Convert.ToBase64String(hashedDataBytes);
    }

Error: The Nonce which is a randomly generated value has expired. Is the code generating a nonce or checksum? Soap UI does not give me this error. It is successful.This is obvious becuase Interoperability is always an issue

SOAP Error, The nonce, which is a randomly generated value, has expired. ocurred while running action:

Thank you