I experienced the same performance issues when connecting to a physical desktop on the local network (using TerminalServer eval, v4.0.366-2 ). This is between 2 machines running Ubuntu 12.04.
My case is similar to the original post in that X is pegged near 100% on the server when connected remotely. The server in on a gigabit link, has 24 cores and 32Gb of memory.
User input is painfully slow as described in the original post.
Is this typical for a connection to a physical desktop?
Should I expect significant improvement if running a virtual session connection?