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
tsclient, terminal, server, rdp, debian, ubuntu, linux, mintthis, upgrading, mint, distro, rdesktop, gnome, entry, aren, fortunately, surprisingly, downloaded, deb, fails, various, dependency, errors, installing, download, https, packages, org, amd,