I tested this yesterday at work before I responded, and just to be sure,
I tested again just now.

1. I opened synaptic, clicked the search button (the binocular icon) and
entered "remote desktop viewer" in the text field on the popup widget,
and clicked the search button on the popup widget.

2. The popup closed, and in the main synaptic window, a list of programs
matching my search came up. Out of the 7 programs listed, 3 of them
were desktop clients, and they are:

tsclient
vnc4viewer
tightvncviewer

So at this point, it's a mystery what happened on your end, whether you
somehow removed your repositories, or you're not running ubuntu as I
supposed... The first step in troubleshooting this is to ask, how did
your results differ from mine, above? At what step did things go south?
Once we know that, we can hopefully figure out what the problem is with
your system.