Now that I've sat down to actually begin work on using this technique with fluids, I've hit another nasty wall: the current algorithm for fluid motion is incredibly dependent on the specific order it's done in for correct, consistent behavior.
This means that doing this in parallel without redesigning the algorithm will result in bizarre fluid movements happening whenever two different threads work in close proximity.
The only way I can think of to get around this problem is to detect whether or not bodies of fluid are connected or not and then assign threads to work on each isolated body of water. The problem with this approach is that it doesn't help at all with one massive body of fluid in motion, along the lines of an ocean.
*Sigh* Looks like parallel block physics is on the back burner again. At least the Tumbler got something nice out of this.