"The user does not have the permission to log on interactively" is definitely the log on locally user right as Answer 2 suggests. There are several locations that this could be changed, but the most likely place is the "Local Security Policy" in Administrative Tools (Control Panel).
In this snap-in open the "Local Policies" icon and click on the "User Rights Assignment" icon. This will show two columns, the "Local Setting" and the "Effective Setting". Scan the list for "Log on Locally" and "Deny Log on Locally". These are the user rights that might be causing your problem.
First compare the list of users in both columns to see if they are the same for both user rights. Group Policies set on the domain, site, or OU in Active Directory will always override the Local settings, so you need to note whether or not the settings were changed on the local machine (likely) or the domain (not so likely). The local column should list the user who is having trouble logging on, or a group that user belongs to (users). If not, double-click on the Log on Locally right and add the correct user or group.
If any users are displayed under either column in the "Deny Log on Locally" remove them (unless they were supposed to be there).
If that doesn't correct the problem you need to investigate the Group Policy assigned to the domain (though a normal user shouldn't have the ability to change that - investigate your permissions in this case)
