Is the terminal server on a domain, or is it a stand-alone server?
If it is a domain member, find out if the user has the correct permissions in the group policy.
If it is a stand-alone, does the user have an account, and is he a member of the TS-users group?
Also, since this is Windows 2003, is this a "real" terminal server with Cals and the like, or is this a server in which users log in using the Remote Desktop function of Windows 2003?