"The local policy of this sytem does not permit you to logon interactively."

You need to do it on the machine that you want to let the user remote into

http://support.microsoft.com/kb/289289

That will do it for you

Check your User Rights Assignment:

Allow log on through Remote Desktop Services
Deny log on locally
Deny log on through Remote Desktop Services

Simplest solution , add him to local admin on XP.

Click Start, point to Settings, and then click Control Panel.
    Double-click System, and then on the Remote tab, click Select Remote Users.
    Click Add type in the user account name, and then click OK.

    If you are adding more than one user name, use a semicolon to separate the names.

Note: Adding users to the Remote Desktop Group requires that you are logged on through an administrator account.

Also, make sure that the Remote Desktop Users group has sufficient permissions to log on through Terminal Services. To do this, follow these steps:

    Click Start, click Run, type secpol.msc, and then click OK.
    Expand Local Policies, and then click User Rights Assignment.
    In the right pane, double-click Allow logon through Terminal Services. Make sure that the Remote Desktop Users group is listed.
    Click OK.
    In the right pane, double-click Deny logon through Terminal Services. Make sure that the Remote Desktop Users group is not listed, and then click OK.
    Close the Local Security Settings snap-in.

(http://support.microsoft.com/kb/289289#LetMeFixItMyselfAlways)

Forgot to mention: I'm working in a domain, so I'm not setting it on the machine itself. Isn't the remote desktop users group sufficient or should I also work via GPO?

Adapted the policy, it is there (checked it) but still same message. Please advise.

Do an RSoP on that machine. It will tell you what policies are being applied to the machine, and if any policies is prohibiting the user from RDPing. Take a look at what motnahpoo stated.

Also logon directly on the machine, right click "My Computer", Properties and select the "Remote" tab. Make sure that one of the  "Allow connection from computers etc." is checked and that "Don't allow connections to this computer" is NOT checked.

Another question - can YOU remote into the workstation or anyone else (admin and non-admin)? Or is only the user having the issue?

I have checked rsop and it is correct, local setting on machine also.
Yes I can remote connect via RDP, that's how I connect always.

Works