This may sound like a silly question but you never know
Are you changing the terminal server port through the registry or simply entering the port number in the RDP connection properties?
Both have to be changed.
That said though, why not simply configure the proxy to allow connection to port 3389?(I know that if you are asking here then you probably don't have access to that so disregard if that's the case).
Out of those 4 ports that you listed as open, your only hope (and it's probably being used internally within the office) is 8080.
Alternatively, you could use something like http://www.logmein.com
(I AM NOT RECOMMENDING THESE... just simply letting you know about them)