It sounds as though you have your laptops setup to only use user authentication, and not machine authentication. If I am wrong, ignore this long winded explanation.....
What I mean by that is that when the user changes the password on a desktop, then goes over to a laptop, the laptop is not on the wireless network yet....so when they log in (CTRL+ALT+DEL) they are logging into the laptop with cached credentials. The reason for this is b/c the laptop is not on the wireless network at the time of user login and can't talk to a domain controller to use the new password. Then, once logged in, the wireless kicks in and requests their new updated password.
I'd suggest you look at enabling machine authentication on the laptops. You don't have to use the "enforce machine authentication" within the dot1x profile if you don't want to, but you should look at the wireless settings on the Windows clients to allow for either user or machine (will show up as host\computername in the user table). If you do this, you'll need to make sure your Radius solution supports machine authentication and that are not doing EAP termination on the controller.
I've attached a screenshot of the Windows 7 configuration option. This is something you can push out with Group Policy if you desire. By allowing the computers to authenticate, you also get the benefit of group policy application at login and logon scripts/etc.