We believe the 'An operation was attempted on something that is not a socket' error is actually a bug in the .NET Compact Framework's System.Net.Sockets.Socket class. In some situations, its underlying handle will suddenly become 'not a socket', making all subsequent method calls on this object fail. Our clients have mostly observed this to occur when a connection or connectivity is lost in some ways. However, a proper behavior would be for the Socket object to throw a different exception, such as 'The socket has been closed', which is still an error, although less misleading.
However, let's get back to the cell provider for now - it's perfectly possible to block explicit FTP/SSL without blocking any ports. All that's needed for that is an FTP-aware firewall that handles unsecured FTP (on port 21) perfectly, while terminating the session as soon as SSL negotiation is attempted (still on port 21). That's exactly what we have observed with AT&T and O2.
Would it be possible to make sure this is not the case with Verizon as well? A simple test would be trying to use a third-party FTP/SSL client app to connect to the same FTP server. If it fails as well over cell phone, it would prove the problem is caused by the cell provider. If you don't have any FTP/SSL client app, try Total Commander 2.52 beta 3 (please note you have to unzip a proper cecmdssl.dll file into its application folder to enable FTP over SSL). Please let me know the results.