Scenario: SBS 2008
TS 2K3 - 30 users
OK, so to save a lot of people a lot of time!
I spent ages trying to diagnose this issue, we had 30 people all getting this message asking for a username and password whenever they opened outlook. I also noticed that if we setup a new user we had difficulty even getting it setup as autodiscovery seemed to keep failing.
Weirdly enough I think it's linked to an update on SBS2008 Ex2007. Check your Exchange to see what rollup it's running (Under Server Configuration - Build No.) You should update it to Rollup V.9 if it isnt already which seems to clear the issue.
A quick note to some people - when you download the rollup and try to install it you'll probably find you can't due to privelidges. I got it to work by opening CMD with run as administrator, renamed the setup to Exchange then just run exchange.msp in the cmd box.