I'm receiving a nonce_used error when trying to authenticate to Jira

I'm working on an application that requires to authenticate to JIRA using OAuth authentication. However I am facing a problem when trying to obtain a request token (/plugins/servlet/oauth/request-token), the request always fails with the "nonce_used" oauth error (oauth_problem=nonce_used). I am generating the nonce randomly, it is a 32 characters long random string containing only lowercase alphanumeric characters. I tried also with longer nonce but with the same result. I am sending the oauth parameters in the Authorization header of the request, but also tried to send them in the body of the POST request with the same result.

Any help is greatly appreciated if somebody already encountered this problem and managed to resolve it.

Cheers,
Istvan