We have a fairly mixed environment, with NT4 on the app server, Win2k on our terminal servers, and remote clients using everything from Win98 to XP Pro. Other than one user with a poor cable modem connection, we've had very few problems. As a matter of fact, since I have an older PC, I prefer to run long routines and reports via terminal services since they run much faster on the terminal server
Some differences between our situation and yours include, 1) that we do have a full T-1, which shouldn't make a difference, 2) we have a dedicated terminal server, which you didn't mention, and 3) we have no idea what we're doing half the time, which means that we might have stumbled onto a setup that works great!
We have as many as twelve concurrent TS users with TAS6-Evo [gee, I hope that Evo-ERP isn't the problem, because we're updating to it this weekend.] We couldn't do more than one or two users with DBA because it slammed the processor needle to redline for minutes at a time, hosing everyone on TS. You might want to have a look at processor usage on your terminal server to see if something is pegging the cycles to the ceiling.
Or I could be all wet. YMMV.