J'ai utilisé BackItUp Pro avec succès - c'est l'une des rares applications que j'ai trouvées qui permet de sauvegarder/restaurer les MMS d'une ROM à l'autre. MyBackup Pro est une autre application populaire. Je n'ai pas d'expérience personnelle en la matière.
Titanium Backup est très bien pour beaucoup de choses, mais pour les journaux d'appels et les SMS, je ne suis pas sûr qu'il soit portable d'une ROM à l'autre. Il semble qu'il s'agisse simplement de sauvegarder directement les bases de données sqlite. Il y a une option "Data Migration" qui a été ajoutée récemment, mais il semble que ce soit une fonctionnalité Pro uniquement. Peut-être que quelqu'un qui l'a essayé peut nous faire part de son expérience.
Il y a aussi Sauvegarde et restauration du journal des appels y Sauvegarde et restauration de SMS qui sont des applications gratuites. Elles sauvegardent dans des fichiers XML, et devraient donc être très portables d'une ROM à l'autre.
Edit : J'ai eu l'occasion de tester les fonctionnalités de restauration hier soir avec le Droid de ma femme. Je l'ai fait passer de Ruby 1.1.1 à CyanogenMod 6.1.0, et j'ai profité de l'occasion pour effacer son téléphone et le redémarrer à zéro. Les applications de sauvegarde et de restauration du journal des appels et de sauvegarde et de restauration des SMS ont parfaitement fonctionné.
Enfin, il y a Sauvegarde des SMS qui copie les journaux de SMS/MMS et d'appels sur votre compte Gmail.