While integrating identica-mode with oauth.el, I ran into an issue where authentication was being rejected if the status update contained multibyte utf-8 characters, which I eventually traced to the last line of oauth-extract-url-params. It seems url-parse-query-string doesn't decode multibyte characters properly, so e.g. "²" would get hexified to "%C2%B2", which is fine to send, but would get decoded to "Â²", which then gets re-hexified to "%25C3%2582%25C2%25B2" for signature generation (instead of "%25C2%25B2") and there you have it, bad signature generation.
I was able to fix the problem by using w3m to decode the hexified url (patch at end of comment), but I know adding a dependency on w3m is a bit of a sledgehammer-y solution. The other solution I could think of was to have the caller provide an un-hexified url, and have oauth.el do the appropriate hexification after signing the request.
--- a/oauth.el 2011-05-22 21:00:41.000000000 -0500
+++ b/oauth.el 2011-06-19 14:47:19.000000000 -0500
@@ -83,6 +83,7 @@
(defvar oauth-nonce-function nil
"Fuction used to generate nonce.
@@ -305,7 +306,7 @@
(defun oauth-extract-url-params (req)
"Returns an alist of param name . param value from the url"
Update, the underlying cause of this issue is fixed in emacs as of 23.3.