Pues como última opción, y por mirar ya donde es raro que pueda haber fallo, entra en los contactos, presiona el botón del menú y entra en los ajustes de los contactos a ver si en la opción esa que hay de "contactos para mostrar" están desactivados los contactos de la cuenta de google o algo.
No recuerdo bien si eso está entrando en el menú de opciones dentro de la app de contactos o ponía opciones de pantalla o algo así, hace ya tiempo que no uso una rom samsung así que no lo recuerdo, pero entra en la app de contactos, pulsa el botón de menú e investiga en unas de esas opciones.