Outlook 2007 client keeps asking for password on exchange 2007

What happens if you do the following on the Client PCs:
Ctl+Alt+Del
Change Password
Insert password details, Old, New, Confirm.

User can change password or just reset it to what it currently is.

After changing password, log off then back on.

I'm having a very similar problem, but did not recently move mailboxes from 2003.  We're running Outlook 2007, Exchange 2007 SP1, Server 2003 R2, Workstations have XP Pro SP3.  I have about 20 users and they're all having the logon box pop up every few minutes.  I'm thinking this may be a recent Microsoft update.  Unfortunately, I updated to SP3, Office 2007 and installed a new Dell switch all within the last month - plus all the regular updates on the workstations and servers.  Thus, too many variables to even know where to intelligently begin troubleshooting.  However, I still suspect a recent update.  I can't believe every user in my organization suddenly has a corrupt profile or mis-matched password in AD.  On a possibly related note, several of my users, after the update to Office 2007, cannot download the GAL (I'm working on that via other posts).  Perhaps Office 2007 has a new security feature that is buggy.

MVDRUM:  If you prefer I not "piggy back" on this question, I'll post my own.  Let me know.

Everyone:  Changing my password had no effect.
I also verified all updates installed on the Exchange Server and rebooted it - twice.  Also no effect.
Also, my laptop is running Vista B'ness Edition and has the same problem as the XP boxes.

sksaathoff: i dont mind at all :)

Im thinking that this has to be related to the autodiscovery service looking for mail.mydomain.com which is still pointing to our old exchange 2003 server..(therefor requireing the 2nd aunthenication).

As our outlook 2003 clients dont get this 2nd pass word request (no auto discovery on them) it makes sense

im going to change the internal dns to point mial.mydomin.com on Monday to our new exchange 2007 server to see if that helps.