The terminal server is especially sensitive to slow networks. This is simply because the entire operating system is transferred over via the network. You should have at least a 100MB backbone for your network and you should be using switches not hubs. Remove the hubs as they will send messages to all computers on the network as they cannot isolate messages to an individual computer.
Ubuntu has several network cards that it is particularly problematic with. I have found that when I experience a slow connection the majority of the time it was a network card that had a bug in the Ubuntu implementation. Check to see if that is the case for your network card as replacing it with a different brand card often made a significant difference.
Another issue that may arise to slow down your network is the ipv6 implementation. Turn off ipv6 in Ubuntu and that may help as well.