Follow Up: I was able to get rid of the CriticalIOException by getting the APN from the Host Routing Table and included it as part of the connection string.
Now I am getting an IOException: Connection Timed Out. I know the Server I am trying to connect to is listening as I am able to send it messages from WiFi and other phones on a Verizon Network. I have successfully set a long Timeout (60 seconds) through SocketConnectionEnhanced but it is still timing out.
It seems like this could be a problem with AT&T or the Telus Phone. Has anyone had similar issues or if you could offer some guidance this one is really puzzling me.