As Grumpy Mike said, 9V batteries are generally not good for much power. Four AA cells or six AAA cells take up just about the same volume, or a little more, and pack a lot more energy.
AA alkaline seem to pack about 2 to 2.5Ahr capacity. To tell the whole story, we need the energy in joules, so the voltage is needed, too.
Alkaline AA Voltage 1.6-1.1V 2.5Ahr
Alkaline 9V Voltage 9-6.6V 550mAhr (agrees with what I've read previously)
We'll inaccurately use the average voltage.
AA 1.35V x 2.5Ahr x 3600sec/hr = 12150 joules x 4 cells = 48.6kJ total
9V 7.8V x 550mAhr x 3600sec/hr = 15.444kJ total
So... over 3x the energy capacity. But that's not the whole story. Using the internal linear regulator, you need 7V minimum to get 5V for the Arduino. So we must redo our calculations again, but with six AA cells and a minimum of 7V for both batteries. However, we must also take into account losses in the linear regulator. In this case, it makes calculations much simpler, but it will be inaccurate because we can't use the entire energy capacity of the batteries, but only down to 7V. So let's chop off 15% of the Ahr ratings and ignore the losses by only considering the energy available as 5V after the regulator.
2500mAhr x 0.85 = 2125mAhr x 5V x 3600sec/hr = 38.25kJ
550mAhr x 0.85 = 468mAhr x 5V x 3600sec/hr = 8.4kJ
A significant difference in capacities.
There are many things you can do to reduce power consumption. If this will be on all the time, a SMPS chip such as the MC34063 can accept down to 5.4V to output 5V (one schottky diode drop) and be much more efficient than a linear regulator when the battery voltage is higher. A linear regulator is wasting nearly 50% of the power when the batteries are fresh.
You might consider using one of the Arduinos that does not have a built-in USB port. That chip consumes a fair amount of power. The Power LED on an Arduino board is also using up power.
Can the ZigBee that you are using be shut down when not required? That could save you some power.
If this isn't on all the time, you could use some of the tricks to putting the Arduino in Sleep mode.
Figure out just how bright the LEDs need to be, and design for the lowest permissible current. Power them directly from the Arduino's 5V supply. Using the 3.3V supply saves you nothing, as it is just another linear regulator and isn't capable of more than 50mA.