I could be wrong, but if I recall from doing desktop support a long time ago, a user on a Windows 2000 desktop can add a network printer just fine, but a user on an XP desktop must have a minimum of Power User rights to do the same, or maybe it's vice-versa

Googhum, are your users on 2000 or XP desktops.