This was a horrible shock after upgrading fromUbuntu 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 variou........
The program itself catches it, just make sure it's actually focused on rdesktop and it sends Ctrl+Alt+Delete to the remote machine and not the local.........