Hola, buenos días!
Continúo con el estudio de la incidencia... Os expongo lo que he descubierto por si le es de ayuda a alguien.
He desinstalado Google Play Services, Play Store y las tres aplicaciones que me daban problemas...
He reiniciado el teléfono y he vuelto a instalar la apk de Play Store 4.3.10. Después he vuelto a instalar Youtube, Foursquare y Runtastic, y ahora funciona todo perfectamente.
Creo que el problema viene cuando Play Store se actualiza de la versión 4.3.10 a la 4.3.11...
Os iré informando. Saludos!