ATmega1284 running very slowly until reflashed
Here's a checklist of a few things that might help further track down the problem:


If you're using interrupts of any form make sure related I/O lines are always being held in stable state. For example if you have a button connected without a pull-up/down maybe external factors are causing it to oscillate. The apparent slowness may be the processor spending all its time servicing interrupts.
Make sure that adequate decoupling capacitors are in place. While that may seem unlikely because programming seems to clear it may also be an oscillator condition that is cleared by physically moving it or applying an external voltage source during programming.
Check that you're generally running everything within specification. For example when dealing with LEDs if you look at the bottom of page 324 ATmega1284 datasheet you'll see that certain groups of I/O pins have a total current limit of 100mA.
You've mentioned the problem is hard to repeat. It might be worth making a note of environmental conditions such as temperature, cell phones being near etc at the time it occurs. For battery operated circuits maybe check the battery voltage at the time, for mains operated think about things like air conditioners that might degrade power quality.
If you've only made a single device if practical it might be worth building a second system in case you've chanced across a bad component or damaged something during assembly / development. If not I'd at least try another AVR.
While not a good long-term solution maybe you could see if enabling the watchdog timer will clear the problem by detecting the slow program operation and resetting. 
You've mentioned around ten times slower. Maybe you could slow down the timing loops by a large amount to give an expected cycle time of say 10 seconds. Then you'll be able to measure the exact time with a stopwatch and get a more accurate idea. If it was exactly 8 times it would indicate something odd with the CKDIV8 fuse. It sounds like you've got that covered by measuring CKOUT but I'll leave it here for the benefit of anyone else with similar problems.