When I upgraded to 12.04 I found that there were problems running rdesktop, especially as I was trying to use shared clipboard via RDP, so I tried the current remote desktop package called remmina and have found it to be excellent. The main problem with this option is that it doesn't import all your previously saved rdesktop connections, but they are human-readable if you open the hidden .rdesktop folder in your profile folder.
As for rdesktop working from a command line, did you fresh install U12 or was it an upgrade from 11.10? If new, you must have installed rdesktop manually, in which case the dash ought to work, or if you copied it as an executable then the system won't put it in the dash. Run the Synaptic Package Manager (if a new installation of U12 you need to install it: sudo apt-get install synaptic). If installed properly, rdesktop will have a green box next to it.
Remmina has the added advantage of sharing a local folder via RDP which shows up on the remote MS Windows machine as an extra drive. It's a good way to transfer files to and from the remote machine. Remmina also allows you to easily scale the remote desktop window, even in VNC. This helps me to manage customers' computers from my tiny netbook.