For some reason I always seem to have problems configuring server side sync with Gmail addresses, and it always seems to be the same setting in Gmail which is blocking the connection, so I'm writing about this to make it easier for anyone else setting up server side sync with Gmail (including myself when I have to do this again).
After seemingly setting up the Email Server Profile and Mailbox correctly, when it came to testing and enabling the Mailbox, both the incoming and outgoing tests failed. This doesn't happen all the time, as I tried to recreate the errors with another new Gmail account, and it tested and enabled first time. However, I had already been playing around trying to connect, so I might have done something to lock down the Gmail account etc.
The Email Server Profile is set up using the correct POP and SMTP settings as per other Gmail recommendations, e.g. using pop.gmail.com with port 995, and smtp.gmail.com with port 587. Credentials are specified in the Mailbox, with everything spelt correctly. However, when testing the mailbox I would receive errors stating that the credentials are incorrect.
There are two hidden settings within Gmail that may be blocking connections from third party apps. Make sure you access these links while logged into the Gmail account, and make sure they're turned on/enabled.
In my case, the first one was already turned on, however after enabling the second one I was able to successfully perform the Test & Enable on the Mailbox.