KE7GKP:
It is not clear what role the Arduino has in any of this? It seems rather risky to even have it in the circuit, IMHO.It would appear that your circuit to produce 3.6-3.7V does not work. You could confirm that with your meter.
If you would like assistance with your voltage regulating circuit, you can start by showing us the schematic diagram.
This small task is a fraction of a bigger project based on arduino that aim to build a water level sensor that can send me SMS through my old nokia 8210 when the water reaches a warning level.
And, not only, it should be able to answer me with an SMS containing the water level when I call him through my cell phone.
To do this, the first step is trying to power my cell phone via arduino board (i could use a charger but, if possible, I would like to avoid it).
My meter confirm that the voltage is correct, but as magician suggested, it is probably a problem of high current needed by the phone.
Thanks