Just to double check, you have changed the IE settings under user authentication logon and set it to prompt for username and password in the same security zone as the user(s) has added your portal webaddress to?"
That is correct
"The password change, is it done when the user is logon to their machine and not through the sharepoint interface via a webpart?"
The password is changed when they attempt to login to the domain and are prompted that their password will expire in "X" days.
Also, to date, no one has had issues accessing anything else. Once the password is changed, they are able to access everything they normally do except the Sharepoint portal.
I try not to approach problems with blinders on because many things can contribute to a problem, but I definitely feel like this is a caching problem. Researching this online I have yet to find anyone else with the same problem and it doesn't happen to everyone here or even the majority, just a small number of people.
To add one more thing to this, those users that can't access Sharepoint are able to if they use Mozilla Firefox. I tried it and it doesn't have the same functionality as IE 6, but they get in without a problem. Maybe reinstall IE 6?