Eso pasa cuando no has guardado la configuración del iTunes antes de formatear. Cuando sincronizas un iPhone/iPod en un ordenador, guardas la configuración en un carpeta de mis documentos llamada iTunes. Esta es la que tienes que guardar cuando cambies el sistema operativo. Si no lo haces, cada vez te va a tocar volver a sincronizar el iPhone de nuevo con el iTunes como si estuvieras en otro ordenador, es una de las pegas de los iPhones.
Un saludo.