Windows determines if the machines have Internet access by attempting to download a small text file. It can tell if you have connectivity when it's able to download, and if the result doesn't match what's expected it then knows you're behind some sort of web login-required gateway.
The whole thing's laid out here.
Seems there's been a full exposé on the topic over at SuperUser.
So my guess is that you're getting this URL (http://www.msftncsi.com/ncsi.txt) blocked. Your options are:
- Disable NCSI
- Run your own NCSI web server and modify the registry to point there
- Unblock the Microsoft NCSI server.