vander,
Assuming you don't already have one, I suggest you get a multimeter so you can measure current. (If cost is an issue, you can get a cheap one for around $10 USD.) You can measure the total current and/or the current draw for the various parts of your circuit to find out where the power is going.
You can look-up how to do it, but current measurement is a bit tricky. You have to break the curcuit and insert the meter in series. And, you have to be careful not to connect the meter (in the current-measurement mode) when there isn't something to limit the current (such as the Arduino or motor, etc.). If you connect a current meter directly across a battery (with nothing in series), you'll get the maximum current from the battery and you'll blow the fuse in the meter. (Usually there is a separate current connection on the meter, so that nothing bad happens if you are measuring voltage and you accidently switch the meter to "current".)
...changed the lm7805 regulator for a 78L05,
That won't help that much. Linear regulators "work" by "wasting" power. The voltage gets divided between the regulator and the load (4V across the regulator and 5V across the load = 9V) and the same current passes through the regulator before going to the load. Power is calculated by multiplying Voltage x Current, so with that set-up, your regulator is consuming almost as much power as your 5V circuit. (There is also a small amount of current used to "power" the regulator, even if there is no power going to the load.)
A switching regulator is more complicated to build (it takes an inductor) but it can be nearly 100% efficient. You can get more current out of a switching regulator than you put in! (But, less voltage = about about the same amount of power.) I believe switching regulators generally take a bit more power to "run the regulator", so they may be less efficient at very-low currents. But, in low-current, low-power, applications, you usually can use a regular 'ol linear regulator, since you are wasting very-little anyway.
I've never built a switching regulator. But in hindsight, I should have use one (or two) on the project I'm finishing-up now!