A mí también me sucedía, al intentar acceder con mi cuenta de Gmail en Youtube me aparecia el mensaje "Google Play Services no es compatible con otras aplicaciones que usan el mismo ID de usuario compartido". Tras probar varias cosas conseguí solucionarlo.

SOLUCIÓN: Instalar una versión antigua de Youtube. La actual versión es la 4.2.16 y necesita Play Services, yo la desinstalé y puse la versión 4.1.47, nada más abrir la aplicación mi cuenta Gmail ya estaba enlazada automáticamente y funcionando.