I noticed randomly “drush uli” would just result in “access denied” when Drupal was inside of a Vagrant machine.
The funny this was, if I waited a little bit, and tried the user login link again, it worked fine.
The problem is the Vagrant machine’s clock may be only a few seconds ahead of your local machine.
So the token that uli generates isn’t valid until then.
Solution: install “ntp” on both your host and inside the Vagrant machine.