Velocity passes should work. I just tried frosting a default Particle Flow, and I got the velocity pass that I expected.
Try changing the Motion Blur Mode to Frame Velocity Offset, if it isn’t already. (You can find this control in the Meshing rollout.)
What is your particle source? The most likely problem is that the particles have no velocity, or Frost is not reading the velocity correctly.
Another possible issue is that we may need some workaround to get velocity working in your renderer. I think this only applies to mental ray, which requires a modifier (any modifier) on the Frost object. See: http://www.thinkboxsoftware.com/frost-motion-blur-modes/
Hey Paul, I am still checking on this, sorry, it does seem to be an fR issue, meaning in the latest build (3.5 SP4) I cannot generate any velocities UNLESS motion blur is enable in the fR render dialog. So this is just different.