My network at work blocks all ports except 80 (HTTP) and 443 (HTTPS). I tried relaying using port 80 and realized that they also have a squid instance that caches data, which basically restricts any access through port 80 to purely HTTP requests. I then decided to relay over port 443 and it worked! So, if you ever want to use a port to get out of even a tightly secured network, try port 443.
For the curious who may be asking themselves as to how I could access Amazon EC2 from my work network, I used the excellent VPNUK service. It only works from my work network over TCP and port 443.