You are very close. The average power is a very accurate way to do this given that you are not pulling such a high current that the effective capacity of the battery fluctuates.
Batteries, Batteries, and More Batteries
There is one very important term, and that is the self discharge rate of the battery. This is dependent on chemistry, but lets say you get a nickel-metal hydride. The self discharge rate is
"20% or more in first 24 hours, plus 4% per day thereafter" if it is not a
low self discharge rate NiMH, which still discharges around 25 or so % a year.
Lithium batteries have some of the best characteristics for self discharge rate and my experience supports this fact. I think battery university has a great site to discuss many different battery characteristics and I often point people there to learn about batteries when they are starting to work with them. If you want to compare battery discharge rates they have an entire article discussing the phenomena.
This is a bit around the point, but I always try to make this point, when you measure battery voltage you need to have it under load. This varies with chemistry, but it is paramount in lithiums. I had a coworker placing bad coin cells in our devices and using them because the coin cells showed almost full voltage with no load. Under a load of any amount(10kohm aprox .2mA) they were flat dead.
Your Microcontroller and You
As you are dealing with using the manufacturer sheet on leakage current there are also many different issues you will have to deal with to keep to those specs that are probably also work thinking about. The biggest I have seen is a floating input. Many engineers will leave unused pins as inputs thinking, "Hey, what harm can this do?" Quite a bit if you are talking microamps. A floating input will have its transistors changing state constantly and the fluctuations cause a power draw difference. We once had a reduced lifetime in a product because we had an error that left 2 pins floating causing our standby current to more then double on our MSP430. You need to drive all of your pins to output and let them hold a state.
It is easy to miss when doing these calculations things like wakeup time. I seem to remember our MSP430 had a non-negligible wakeup time if you were doing it very often. It also had a larger power pulse for just a moment as it came online. Our little homespun RTOS had to try to take this into account and if the shutdown was less then X milliseconds we skipped it with NOPs and saved some power.
If you are looking at a very long life product, you are going to need conformal coating. The oils in your skin are not an issue immediately, but with time they form a lightly conductive material on your board. Conformal coating protects your board from this little current sucking side affect.
Read any app notes they have about low power operation, it probably covers issues like the pins need to be held as output and many other important and useful facts.
Last but not least, Dont let yourself get relaxed just because you have read the app notes and everything seems okay after a week of running your product, you have to do as clabacchio says, you must measure and make sure. You debug your code normally, this is part of it, you need to find out if you made a mistake that is causing your idle current to be mAs instead of uA or even just if you did what we did and a pin is floating on accident. Make sure you use buffered measurements when you do this, if you have a large leakage on your device taking the data you can make a mountain out of a molehill when testing. Also, never forget about pullups, they are little power hogs if you are not careful.
Just an add on to the already excellent comments here, If you are going to use your cigarette lighter plug to "jump start" a vehicle with a low battery, Do not expect to plug your jumper pack in and turn the key. The wiring for the lighter plug is not designed to carry that many amps. The answer to this is to plug the starter into the lighter socket, then wait about 15 minutes for the battery to "charge" your car battery, Then UNPLUG your jumper battery and then attempt to start the vehicle.
Best Answer
Guessing without a datasheet is not the best. You can expect that to use around 25mA give or take 10 or 20mA. Let's say 30mA and 30 seconds and you will power it at 6V and allow it to fall to 4V (average voltage 5V and assumed constant 30mA, which won't be true, but is close enough for a WAG without a datasheet).
So \$C = \frac {2(0.03 \cdot 5 \cdot 30)}{V_f^2-V_I^2}\$ = 0.45F
Since the energy consumed is the integral of i(t) * v(t) over time, and the energy in a capacitor is \$ \frac{C V^2}{2}\$