So after my (unrelated) issues with clone Arduino Pro Mini boards ( http://forum.arduino.cc/index.php?topic=426589 ) I decided to just forget about them and built myself a simple breadboard arduino.
Basically I took an ATMega 168-20PU, added an 8MHz crystal and two 12pF caps plus a 10uF cap and whacked everything on a breadboard. I programmed the Arduino Pro ATMega 168 3.3V 8MHz bootloader onto the chip and that was it. When the thing is powered from 5V everything works just fine.
My sketch does some serial communication and I've also added an LED (that turns on in setup) just so I can see what is going on.
When I apply 3.3V the thing does nothing. It draws around 3mA of current (compared to 9mA when powered from 5V) but it doesn't work. There is no serial communication (I am using a 3.3V serial adapter) and the LED stays off. At first I thought that a small LDO that I was using wasn't providing enough current. So I tried a large 800mA LDO powered from an arduino 5V supply. And nothing.
I've also tried a lithium cell (at the time it was providing 3.8V) and that worked fine. I have no idea why 3.8V would work but 3.3V wouldn't. As far as I know ATMega 168 should run just fine from 3.3V.