I recently battled this. I found a great javascript signature calculator at:
http://oauth.googlecode.com/svn/code/javascript/example/signature.html
It signs in your browser, doesn't hit their server, so you can enter all the keys and secrets. You can enter the timestamp and nonce generated by your OAuth library, as a double check.
What language & OAuth library are you using for the OAuth parameters & signature?