A mi me pasaba lo mismo al actualizar manteniendo datos y se solucionó con este método que ya se ha comentado varias veces por este foro:
Ajustes > Aplicaciones > Todas >Teléfono
le das a Borrar datos
y reinicias el teléfono.
Aunque para tu caso no se si servirá si dices que ya has reseteado el teléfono completo.