The conditions I'm experiencing are similar to what this guy writes about: Arduino Forum
I have noticed something else; adding a blink, the blink works correctly on start up every time. But the Tx LED doesn't flash when it should- regardless of hardware restart. This shows that the program is running fine, but unable to transmit data via USB.
This suggests that the FTDI serial adaptor isn't able to communicate with the chip on start up.
Surely this issue has been documented somewhere else? Anybody come across this problem before?