There seems to be an issue where certain characters in the signature are creating validation to fail. Here is an example (using HMAC-SHA1 for signature method):
Signature as generated on the consumer side (using CoreOAuthConsumerSupport to make the call): KoCR1Z1PeM/+sCoptySENMEh2xw=
Signature as generated on the provider side: KoCR1Z1PeM/ sCoptySENMEh2xw=
Notice how the + is missing on the provider side. My guess is this has something to do with URLEncoding/Decoding. This is difficult to replicate since the signature needs a + sign in it after generation.