Te voy a dar la solución a tu problema, y sé que funcionará porque hace dos semanas me pasó exactamente lo mismo.
Lo único que tienes que hacer es dejar presionados los botones para entrar en modo recovery más tiempo de lo normal (Home + Power on/off + Volumen down), el equipo se reiniciará de nuevo y parecerá que no entrará en el modo, pero sigue presionando por 10 o 15 segundos más sin soltar ningún botón y allí entrará ahora sí en modo recovery. Toca instalar nueva rom eso sí.