ATmega64 needs to be reset after Power Up
Some hints:


AVRs have clock startup delay fuses (SUT1/SUT0 for ATmega64) - check if problem happens at different settings of the startup delay.
Use brownout detection (also a fuse setting).
Try adding a busy-wait loop at the beginning.