Up the physics update rate until it works, it doesn't have to coincide with the framerate. I'd always do my timing like:

    physicsStep=10
    nextUpdate=currentTime()
    while(1){
        while(nextUpdate<currentTime()){
            doPhysics()
            nextUpdate+=physicsStep
        }
        doRender()
    }

Even on a mobile phone you'll probably get away with a pretty high update rate.