I'm having problems validating also, and would really like to know something - My base strings match up exactly when using the Oauth Tool, or at least they appear to. Is it possible that, although they are showing the same characters, they could still be different through character type?
Other than that, I have no clue why it's not ...