While I've not seen this before, I can offer some initial testing steps. First, I recommend installing IISCrypto from Nartac Software, clicking the Best Practices button, applying the changes, and then finally rebooting the server to allow those changes to take effect. 

This will configure your server to use only the TLS/SSL versions which are currently not vulnerable (TLS 1.2+) and should ensure your server is able to support whichever protocol versions are in use on the Gmail side. Please note however that this can cause connectivity issues for email clients and mobile devices which have not been updated recently, as they may be using an unsupported version of SSL/TLS. 

Beyond that, does this affect all messages coming from Gmail or only specific messages? If specific messages; is there anything about the content in that message which might be causing the connection to be terminated for security or antispam reasons? 

Thanks for your response Kyle !!

Currently only emails sent from Gmail are failing and getting bounced back. The test emails sent from Yahoo/Hotmail etc seem to go through just fine.

I read this to mean that your BEST crypto options are worse than Gmail MINIMUM crypto options.   Ensure that you have enabled TLS1.1 SHA2 and AES-256.

If you are still running an old version of SmarterMail on an old version of Windows, you may need to upgrade your server.

Your problem is best explained as a change in Gmail's configuration to enforce better encryption.   You should assume this is a permanent change.

Your MINIMUM encryption options are unlikely to be a factor, so you can leave TLS1.0 enabled if desired.   I have posted previously that disabling TLS1.0 caused some sources to be unable to send to me, because they did not fall over to unencrypted mode.

I am on SmartMail 14.2 so guessingI am on TLS 1.2

TLS1.2 is what you need.  

It is all about the Windows version.  I guessed an old version of SmarterMail because the newer releases of SM require the newer versions of Windows Server.  Here is my recollection:

- On Windows7 (and therefore perhaps in Server 2008 as well), TLS1.2 was present but disabled by default in early releases.  It could be turned on manually, and then a Windows Update kit eventually turned it on by default.   

- For Server 2003 and 2003 R2, there were Windows Update kits to add support for TLS1.2 and AES256

I don't recall any special measures required to enable current encryption components in Server 2008 R2 or later.

TLS (and its predecessor SSL) is the protocol - how do I say "Hello" and "Goodbye".   TLS1.1, TLS1.0, and SSL3 have been deprecated as vulnerable to specialized attacks.

After connection, an asymmetric encryption algorithm is used to discuss what comes next.   I think some the options are RSA and DH and ECDH, and ECDHE.  These are high-overhead algorithms, so the peers use this connection to select a symmetric encryption algorithm and choose a key.  

AES and 3DES are examples of symmetric encryption algorithms.   A bunch of older algorithms have also been deprecated as vulnerable.  A bunch of newer ones have also been rolled out but I forget their names.

A MAC (checksum) algorithm is used to ensure that a packet is received in the same form as it was transmitted.   The preferred one is SHA2.  SHA and MD5 have been deprecated as unsafe.

PFS (perfect forwarding secrecy) is a reset mechanism which helps to ensure that cracking one packet does not allow the attacker to crack all packets.   Sessions without PFS are generally deprecated also.

The number following some of the protocols is bit strength.   For example, AES-256 and SHA2-256 mean that 256 bits are used for the algorithm.   Higher bit strength is harder to crack using brute force techniques.

I did not understand all this layering until I started studying for the CISSP exam.   The chapter on encryption explained this all in language that I found easy to follow and understand.   Above is my attempt summarize a complex topic.

As I said originally, you should be able to talk to anybody as long as your server can do TLS1.2, AES-256, and SHA2.  Best wishes.