New users cannot connect to terminal services from a Vista compute

Hi,

We have several users connecting to our Windows 2008 Terminal Services
servers via remote desktop. Most users connect from remote offices or their
home computers. When we create a new login for these remote users, we select
the option "User must change password at next logon". This worked fine when
users were connecting from Windows XP and Windows 2000 computers. They would
be prompted to select a new password when they login first time and once they
change password, everything worked fine. We decided to start buying computers
with Vista (probably a mistake) and our users are unable to connect. They get
an error message that says "You must change your password before logging on
the first time. For assistance, contact your system administrator or
technical support" and disconnects. Is there a workaround for this problem or
do we need to just go back to Windows XP? Any help would be greatly
appreciated.

Thanks,
Venu