I was having this same problem. The library I was using (ObjectiveFlickr) maintains a context which has a data structure for holding OAuth token and secret. Unfortunately as part of the OAuth "dance", those same fields are used in one step to hold the request token and secret and it is up to the user to replace them with the OAuth token and secret later on when they are granted.
The moral of the story is that if you are seeing this error, you are making an API request using an already-used request token instead of OAuth token.