Sembra appunto un problema del servizio Kies sul telefono.
Il firmware indicato nella tua firma è un po' vecchio, potrebbe essere quello il problema: prova ad utilizzare versioni più vecchie di Kies, ma se riesci, aggiorna quanto prima.
In questo modo, con un firmware tutto nuovo, non dovresti più avere l'errore lato telefono.
Altro tentativo che puoi fare è impostare la connessione USB, che immagino sia in modalità Kies, su "chiedi alla connessione"
Poi riavvia il telefono e prova a riconnetterlo, dando la risposta giusta quando ti chiede di connettere l'usb
Prova...