Yeah the problem with that tutorial, is he uses a pullup resistor to trigger the AVR out of sleep mode (And he does it on pins 8-13... wtf?), which is a large drain on power. Your best bet is to use UART, or externally pull a pin down, and then flip it HIGH rather than LOW on the interrupt. This allows for zero I/O power usage, while still maintaining the interrupt.
Glad to hear the new battery worked out for you, time to make the Arduino do all sorts of cool stuff for ya now that you don't have to worry if your car is going to start in the morning