Today I ran into this error while requesting a new request_token.
After checking my code over and over again I used the oAuth tool from this very website and checked the curl code provided.
I still get the same error.
I read the oAuth FAQ but my systemtime is in time and my nonce is good to go.
My signature cannot be invalid if your oAuth tool is working ( which i assume