J'ai eu le même problème. Après une synchro (réussie) en 3.1.3 - donc avec une sauvegarde - , j'ai restauré l'iPhone en me basant sur la dernière sauvegarde réalisée.
Après quelques heures, j'avais l'iPhone 3G en IOs4 avec mes données applicatives préservées mais certains réglages perdus (le mot de passe du téléphone).
Patience...