Why does Twitter sometimes not authenticate on the first attempt through my application


We are using OAuth to authenticate our Twitter application. The work flow is:

  1. User accesses website
  2. Use is taken to Twitter to login and give our application permissions (if its the first time logging in)
  3. Redirect to callback_url

However, on certain occasions (specifically if the COMPUTER has never come to our website before), the person is redirected to our website and they are not logged in. It is as if they never even went to the twitter login screen. However, once they login again, they are logged in properly. This started happening recently. Anyone else run into this type of issue? Thank you.