This was resolved. It turns out our IT Staff was correct. Both TLS 1.1 and TLS 1.2 were installed on the server. However, the issue was that our sites are running as ASP.NET 4.0 and you have to have ASP.NET 4.5 to run TLS 1.1 or TLS 1.2. So, to resolve the issue, our IT Staff had to re-enable TLS 1.0 to allow a connection with PayTrace.
So in short, the error message, "the client and server cannot communicate, because they do not possess a common algorithm", was caused because there was no SSL Protocol available on the server to communicate with PayTrace's servers.
UPDATE: Please do not enable TLS 1.0 on your servers, this was a temporary fix and is not longer applicable since there are now better work-arounds that ensure strong security practices. Please see accepted answer for a solution. FYI, I'm going to keep this answer on the site as it provides information on what the problem was, please do not down-vote.