Your first GameOverlay Test did not help. Ran around 17 fps, same as before. Touching the screen still helped to increase fps.
The resolution change helped the problem the most.
In 960x720 fps was 20-25 - a little choppy sound/gameplay
In 800x600 fps was 25-30 - pretty smooth gameplay, hiccups occasionally
and 640x480 was 28-30 - pretty much perfect, however a bit too small to play on due to the native resolution being 1920x1080 on the S4.
Though in all of these resolution modes (and native) I noticed still if there is any input such as me touching the screen - (making it produce the little dot where my finger is) or opening/closing the menu, the fps will jump up to a constant 30+fps
So the resolution is a work-around for the problem at the moment, but there is still something else that is making it lag.
--Btw, these fps values same with the version littleguy set me