A que le llamas "liberado mediante IMEI" ? , le han cambiado el IMEI para liberarlo ?, si es así deberás ir a quién te hizo el trabajo a que te lo solucione ya que al actualizar pasa lo que a ti, el teléfono o no tiene red o en algunos casos se reinicia constantemente.-
Si esto no es así, lo del IMEI, entonces puedes tener problemas con la batería que ha comenzado a fallar, ponle otra de otro S4 o de algún S3 que también te funciona en el S4 y pruebas a ver si sigue el problema.-