Segun tengo entendido tienes que instalarlas todas desde el Market para que te las reconozca. Por eso mismo aun no he hecho ningun wipe, por la pereza de reinstalarlo todo...
Por cierto, con el MyBackup salvo las aplicaciones te lo ha restaurado todo correctamente?