In that video, it looks like they gave one (or a few) butterfly a path constraint and then duplicated it a bunch of times, which is an option for you. You could birth particles off the object on the path. Or you could point cache the object on the path constraint, change the position controller back to Position XYZ (to get rid of the path constraint), and use that as an animated shape instance in pflow.
I worked on the previous file a litte and I think the particles have a smoother motion, but they don't have that round arc I think you're looking for. I added noise and waveform controllers to the divergence in the speed ops to give them some random divergence. But if you need that round arc, I'd go with the path constraint.
pflow_random_motion_b__max_2009_1.zip
3ds Max 2009 SP1, 2010 SP1
Maya 2012
Windows 7 Professional 64-bit
Dual Intel Xeon E5520, 6 GB Ram
NVIDIA GeForce GTX 460 OC