This is a constant problem for me as well and it was present in 9.04, 9.10 and now 10.04. My current Ubuntu build is:
Ubuntu 10.04 LTS \n \l
Linux box1 2.6.32-21-generic #32-Ubuntu SMP Fri Apr 16 08:09:38 UTC 2010 x86_64 GNU/Linux
The problem is not present when connecting to Windows 2008 servers, only Windows 2003 servers. I'm using RDPv5 in the tsclient settings. It's a very annoying problem. I connect to a Windows 2003 server and the window comes up. Sometimes the problem occurs right away in that I cannot login because of network issues (I guess, with the tsclient) and the session freezes and disconnects. Sometimes I can login but the session freezes just after that and finally disconnects. If I use a Windows client/OS these issues are never present on any server I connect to with RDP so it seems as if something is broken with the Ubuntu package(s).
I have tried fiddling with the tsclient/rdesktop options to no avail.
I run tsclient -vvv from the CLI and here's what's in the console for a session that fails.
cd@box1:~$ tsclient -vvv
(tsclient:17124): GLib-GObject-WARNING **: /build/buildd/glib2.0-2.24.0/gobject/gsignal.c:3079: signal name `depressed' is invalid for instance `0x1988800'
** (tsclient:17124): WARNING **:
Autoselected keyboard map en-us
WARNING: Remote desktop does not support colour depth 24; falling back to 16
ERROR: recv: Connection reset by peer