Вы правы насчет метода подписи.
Но моей главной проблемой было то, что я неправильно обращался с токеном. Вот рабочий код:
consumer = oauth.Consumer('key', 'secret')
client = oauth.Client(consumer)
# Get access token
resp, content = client.request('https://www.instapaper.com/api/1/oauth/access_token', "POST", urllib.urlencode({
'x_auth_mode': 'client_auth',
'x_auth_username': 'uname',
'x_auth_password': 'pass'
}))
token = dict(urlparse.parse_qsl(content))
token = oauth.Token(token['oauth_token'], token['oauth_token_secret'])
http = oauth.Client(consumer, token)
# Get starred items
response, data = http.request('https://www.instapaper.com/api/1/bookmarks/list', method='POST', body=urllib.urlencode({
'folder_id': 'starred',
'limit': '100'
}))
res = simplejson.loads(data)