Token not found

I am trying to set up 2-legged OAuth on my server, in combination with the Services module, to set up a REST server. I actually had it set up for 3-legged, so I know it was working. Next I changed 3-legged to 2-legged on the Service authorization page within Drupal. I'm using the following PHP script (that uses the Oauth-php library) to connect to the web service:

$options = array
(
	'consumer_key' => CONSUMER_KEY,
	'consumer_secret' => CONSUMER_SECRET,
);

OAuthStore::instance('2Leg', $options);
$params = null;
try
{
	$request = new OAuthRequester(BA_REQUEST_TOKEN_URL, 'GET', $params);
	$result = $request->doRequest(0);
	parse_str($result['body'], $params);

	/*
	Note: $params looks like this:
	Array
	(
		[oauth_token] => AB2MagmyJsNiEKDBBcBUyPUxfTLEw7rD
		[oauth_token_secret] => BFEtaonGmVKxg33BjmuWjdh4fhi5unbj
	)
	*/

	$request = new OAuthRequester(RESOURCE_URL . '/message/828.json', 'GET', $params);
	$result = $request->doRequest();

The result of said call is:
Request failed with code 401: ["Token not found"]
I've done a lot of debuggin
I've looked at the {oauth_common_token} table, and I'm seeing the key and secret are in there. I do notice that each time I make a new request, it adds a new row to the table, is that correct? Is it supposed to happen?

I even checked the sha1() of the hash, and the hashed value properly shows up in the hash column in the DB table. I haven't confirmed that these values are correct at the times when they should be, but through some testing, I've determined that these values are all correct in the database at one time or another.

But, that's as far as my debugging has gotten me. Googling isn't helping, DO searches aren't helping. Help!