The parameters must be sorted in natural (strcmp) order. So oauth_token should come before oauth_version in your base string.
Are you passing the authorization via get parameters or authorization headers? If get, then post the entire url here. If via headers, then post the Authorization: header here. Check to make sure that things are encoded properly.
Are you passing any query parameters to the contacts end point that you didn't include in the base string?
Are you using the correct token secret that accompanies that oauth token?