This was a horrible shock after upgrading from Ubuntu 9 to Linux Mint 17 and I found that the last distro to support tsclient was Debian Squeeze.
For some reason it has disappeared for a long time and the new options such as rdesktop and gnome-rdp do not have any start menu entry and just aren't done as well as tsclient.
Fortunately there is a solution:
tsclient surprisingly can be downloaded as a direct .deb package and it fails with some various dependency errors when installing but works just fine.
You can download it here: https://packages.debian.org/squeeze/amd64/tsclient/download