Pues, si lo de servidores remotos no te salía antes, está raro, no sé que pueda ser.
Lo del cambio del imei es no sólo ilegal sino jodido. Acabas de perder cualquier soporte del servicio técnico ó de tu operadora en caso de que haya problemas con el servicio de teléfono ó datos. Si el imei es genérico, puede que te quedes sin llamadas, si lo llegan a bloquear tendrás una mini tablet con wifi, ya no un móvil.
Edit: esta app te puede ser útil para ver qué está pasando.
Network connections:
https://play.google.com/store/apps/d...ll.connmonitor
También considera rootear el móvil e instalarte una firewall tipo droidwall para controlar mejor el tráfico de datos.