it may just be the wrong part for the job.
According to tests on the web (I included a link to one below), 2N2907s seem to work. However, based on the fact that the transistors are heating up so much, I definitely agree with you on the saturation issue. The models I used for making the H bridge never mentioned an Arduino, so the resistors recommended there are probably for a higher amplitude current.