Telnet through Proxy/Firewall

We have just set up a DSL connection at the law firm I work for. We have a SonicWall firewall connected to a server running Proxy Server, which then connects to the network. The attorneys use a research software package that uses Telnet, and it isn’t working. Telnet from start:run doesn’t work, either. They work on my PC, but not the attys’. I gave permissions to “Everyone” and “domain users” and a specific attorney to Telnet and Everything (I forget exactly what it was called) on the Proxy Server, and allowed outgoing Telnet on the Firewall. Any ideas?