I'd be tempted to use a PICAXE to switch the power on and off to the Arduino. You'd only need an 8 pin cheapo with a transistor to switch the current. The basic sleep mode on the picaxe 08 is a few tens of microamps and less than a milliamp fully running. Its not like they are expensive....