You'll need to provide a little more information if you want help:
* which error message do the users get?
* is there any EventID in the EventLog on the terminal server when
the users try to connect?
* which OS and SP do you run on the server and the client?
* which type of licenses? Server CALs or TS CALs? (you'll need both).
* does this problem occur on all clients, all users, or only some
clients, some users?
* does it work for Administrators?
* can the clients ping the server?
* is the server listening on port 3389?