Trouble using OAuth with Services

I have been using Services 6.x-2.4 with Key Authentication via XMLRPC. In the most recent upgrade to my website, I have been getting authentication errors (session ID sent instead of data on first attempt, second attempt is successful).

Since 2.4 is no longer supported, I though I would upgrade to Services 6.x-3.1, a REST server and 2-legged OAuth.

I have been able to implement the REST server by authentication eludes me. These are the steps I have followed:

1) Install the Services 6.x-3.1 module and OAuth 6.x-3-beta4
2) spyc.php installed
3) Enable OAuth and OAuth Provider UI
4) Enable Services, OAuth Authentication, REST Server (as well as Chaos Tools and Autoload)
5) Create an OAuth context retrieve_user at admin/settings/oauth/add for retrieving user information, checking only the HMAC-SHA1 signature method (this is very poorly explained)
6) Install the patch from http://drupal.org/node/1336974#comment-5298386 which adds the 2-legged vs 3-legged authorization option below
7) Add a service at admin/build/services/add with endpoint test_rest_oauth
-Server: REST
-Debug mode enabled
-OAuth authentication
8) Service options
-Resources: user.retrieve
-Server REST defaults
-Authentication:
-OAuth context: retrieve_user
-OAuth authorization level:
-Required authentication: Consumer key, also known as 2-legged OAuth

9) Create a user which will act as the consumer.
10) Select user Authorization tab
-Options are "Authorizations", "Consumers", "Add consumer"
11) Select "Add consumer" for this user
- Enter consumer name
- No callback (what is this for? automatically filled as 'oob')
- No application context is available
- Save and key and secret are generated

So far no luck - any words of wisdom out there? Thanks.