A 9v battery can not supply enough current to make most phones happy. A 9v battery is designed for... maybe peaks of 100-200 mA. The standard usb is 5v at 500mA and some phones use up to 1A. As the phone pulls lots of current, the voltage will drop from 9-10v down quite fast.
A 7805 needs about 6.5-7v to output 5v, and the 9v battery will go down to 6.5-7v levels if you pull a lot of current.
Post the schematic as tautech says, let's see how you connected everything.
Some phones won't charge if the data wires/pins are not used in some way. Older apple phones want to see some voltage on those two data wires, which can be done with 2 sets of resistors. New usb charging standards say the two data wires have to tied together, other phones expect a resistor between those data pins.
This page explains how to configure the data wires to simulate an apple charger :
https://learn.adafruit.com/minty-boost/ichargingps. In addition, 7805 is a linear regulator, and a very poor way of providing energy to a phone. With linear regulators, current goes in, same amount of current goes out, just voltage changes. So the higher the voltage difference, the worse efficiency. With 10v in (fresh 9v battery), 5v out, you're looking at 50% efficiency, which is very bad, you're wasting half the battery as heat in the regulator.
Even a basic mc34063 dc-dc converter will start from about 65-70% efficiency.