I have exactly the same problem with my xAuth app.
On first run the user enters their password, and my app retrieves the correct oath_token and oauth_token_secret. These credentials are used to make a request for home_timeline, and it comes back with “Could not authenticate you.” This is not a 401 error, but a valid response.
After quitting the app and restarting, identical (cached) oauth_token and oauth_token_secret are used. This time the request for home_timeline is successful!
Very careful comparison of the requests, one of which fails and the other of which succeeds, reveals no obvious differences, except for expected differences in the nonce and signature.
I’ve gone through this exercise at least 50 times, always with the same result. It seems obvious that my auth code is working fine. Not only does it seem to be working fine, based on a dump of the requests, but it has been working fine for several years now. I haven’t changed anything–but this problem has only cropped up recently.