The subject behavior is the result of having a newer version Xenroll.dll on your Windows Server 2003 CA than the user has on their computer.
To alter this behavior:
1. On your server, open %SystemRoot%\System32\Certsrv\Certdat.inc in Notepad.exe.
2. Locate the sXEnrollVersion="5,131,3686,0" line.
3. Alter the line to read sXEnrollVersion="5,131,3659,0".
4. Save the file.
5. Exit Notepad.