I was getting this issue, too.
I was encoding the value for oauth_callback in my authorization header, because that’s what the Example request tells you to do. Straight from the doc:
oauth_callback="http%3A%2F%2Fmyapp.com%3A3005%2Ftwitter%2Fprocess_callback"
Remove the encoding in your header to fix the issue. E.g.
oauth_callback="http://myapp.com:3005/twitter/process_callback"

Edit: Actually, I’m using a library to handle the OAuth headers, so it’s quite possible that the value of oauth_callback was double-encoded (I encode it once, the library encodes it a second time), as kurrik mentioned. In which case the docs are correct as is 