Desconozco si el teléfono de tu pareja también es Samsung pero si lo reconoce y se conecta, está claro que el problema está en tu móvil. Igual ya lo has hecho, pero lo único que se me ocurre (lo que yo haría en tu caso) es borrar todas las conexiones desde el multimedia del coche y desde el móvil e intentar conectar como si fuera un teléfono nuevo. Si nada de eso funciona, probaría primero a reiniciar el móvil, luego a restaurarlo con una copia de cuando no tenías problemas de conexión, por último restaurarlo de fábrica (sé lo que supone) y por último cambiar el teléfono por el de tu pareja (si ambos estáis de acuerdo). Si nada de eso funciona, me plantería vender el móvil y comprar uno nuevo.
Un último consejo, puedes llegarte por el concesionario donde compraste el coche y preguntar (no sé qué tiempo tiene tu coche o si te pilla muy lejos). Mucha gente ha tenido problemas de este tipo y el del concesionario se lo ha solucionado en un momento. Más no te puedo decir. Suerte.