Marvin Martian -- if all you want to do is reduce power consumption, then you can change the clock speed once you've booted (in your setup function), as described above.
I posted some test figures earlier in the thread, showing the reduction in current for various clock speeds. If it's possible to put the arduino to sleep for longish periods of time when it's not doing anything, then this will save power further.
If you want to run on a LOWER VOLTAGE, then you may need to reprogram the bootloader to get the arduino to bootup on that lower voltage, depending on how low you want to go.
I'm basing this assumption on what we found in the ATmega328 datasheet, again mentioned earlier in the thread.
I'm beginning to think it would be GREAT to have a slightly modified bootloader that selected clock frequency based on some jumpers on the board. Anyone fancy giving us an early christmas present...? 