I've managed to work around this by changing the API host name from 'api.instagram.com' to 'www.instagram.com' for the Oauth authentication flow.

Here's my fork for the omniauth-instagram Ruby gem, which is now allowing me to consistently log in: https://github.com/stefl/omniauth-instagram/blob/master/lib/...