This Microsoft article has some relevance on how to setup your terminal server: http://technet.microsoft.com/en-us/library/cc753853(v=ws.10).aspx, so make sure you've at least followed it's instructions.
Basically, you need to make sure drivers are available on the terminal server (of the correct version and bit-ness) for every printer people are using. Yikes! If you're lucky, they have mostly the same printers. If not...
To get the drivers, most printer manufacturers have several available driver packages. Look for ones that say something like "minimal", "network install", or "basic driver". HP for example has "full feature software and driver" or "Basic Driver".
These ones are usually either ZIP files or self extracting EXE files that will give you the real .inf and associated files that you can add to the server.
If those aren't available, you can either run the full installer on the terminal server (but that will also install all the printer helper program stuff, which you almost certainly don't want), or start the setup, then look in %TEMP% for the files it extracted there, copy them elsewhere, and cancel the installation.
Alternatively, you can use something like ThinPrint which doesn't require unique drivers for each printer. But it does require that the ThinPrint client be installed on the computers of everyone connecting. (This is not necessarily a recommendation for ThinPrint...there are also other ones that do the same thing, which might be better. I've used ThinPrint before, and it does work.)