I did not look into narkoleptic in detail but it seems that at least some timer will still be running.
My experience in pushing power consumption of the controller down to some microamps are:
1) read the datasheet. It not only about stopping the CPU.
2) if possible cut of all peripherals (not sleep them, but really cut them off). The datasheet explains how
3) if you can not cut off everything lower the clock (by means of CKDIV) before going to sleep, do not forget to speed up after waking
3b) do not lower the clock for at least 1s after a reset, otherwise you might virtually lock you out.
4) Ensure that all pins are either output or pulled to a defined state. Avoid free floating inputs at all cost
5) Use a board with a different regulator. The default power regulator of Arduino will draw to much power even if everything else sleeps. If it is an uno, think about how to sleep the processor for the serial interface. Or as suggested: do not use an Arduino at all, use a stand alone chip
It is fairly easy to get the controller to an average consumption <1mA. <100uA gets harder. 10uA is possible but you start getting all kinds of weird effects, e.g. seemingly being unable to power down the controller because it will be powered through some pullups.
If you want to push it you will have to look into the datasheet and use a customer board. Decreasing Voltage is also a good idea, but this implies that you have to decrease the frequency as well. The RC oscillator will use less power as a crystal. Crystals with lower load will consumer less than crystals with higher load.
You may also want to look here http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1283746054/0