Twitter oauth/request_token failing sometimes

Question

Hello there.

I'm implementing Twitters OAuth for Adobe AIR in Javascript. My problem is, that out of 100 requests to api.twitter.com/oauth/request_token about 30 fail with the usual error message: Failed to validate oauth signature and token

The other 70% of requests produce a correct response, so I believe that my algorithm for signing is correct.

I've read about invalid timestamps in a lot of forums and mailing lists but that is not the problem. My timestamps are correct.

I also checked, if the nonces are unique, so that's not the cause either.

Any ideas why this is happening?