Next I tried the command line way, 'net use'.
net use z: \\SERVER\shared_folder /user:Username Password
Again kept staring at the error message: System error 86 has occurred. The specified network password is not correct.
The solution I found, after hours and hours of googling...
On the WinXP machine, go to Control Panel -> Admin Tools -> Local Security Policy -> Local Policies -> Security Options -> Network security: LAN Manager authentication level -> change this value to Send LM -> NTLM responses.