Yo llevo la última 4.2.2 de mackay y me va muy bien de siempre con ella. No recuerdo haber tenido ese tipo de problema con el móvil y mackay, aún teniendo un montón de juegos y aplicaciones instalados.
Probaría con diferentes modems y si aún así te sigue pasando con una instalación limpia de la ROM podría deberse a algún problema físico del móvil, si no, volvería a probar con una instalación limpia desde cero o con alguna otra ROM o metiendo alguna de las últimas oficiales de samsung.