When you install a program on a terminal server you should set the server in install mode. If you don't do it the application installed will work fine for the user that installed the program but not for other users.
This has to do with the "shadow bits" to the HKCU registry and users ini-files.
I don't know what program you're installing, but I would try to uninstall it, set the server in install mode (with none users logged on) and try to install the application again.
I have experienced once that once installed in execute mode the application never worked even if it was uninstalled/installed.
Here is the step you should take:
1. Uninstall from add-/remove programs
2. Open cmd and type:
3. change logon /disable
3. query user (only the consol user should be logged on)
4. change user /install
5. INSTALL THE APPLICATION
6. change user /execute
7. change logon /enable
Then try the application with a normal user.
SG