Hace unos meses esta pérdida de IMEI se podía recuperar con este firmware que te pongo para que descargues desde 4Shared, se flashea igual que uno común, por Odín :
Galaxy S4 Fix IMEI
Usa el Odín 3 v3.09 que es el que mejor va para el S4, sino también puede ser el v3.07.-