I'd been the same problem with 2-legged oauth, I fixed with:
consumer = OAuth::Consumer.new(key, secret, { :site => 'http://api.mysite.com' })
access_token = OAuth::AccessToken.from_hash(consumer, :oauth_token => key, :oauth_token_secret => secret)
Common issues comes from out of sync timestamps
Your requests must be synchronized with the server system clock, for instance in linkedin must be within 5 minutes of her system clock.
Hope it helps ;)