Looks like this week is all about synchronicity.. That effect looks very similar to the one I'm using I was looking to do the same thing with the randomization on my own current map. I ended up being happy with the way it looked as is, so I did not pursue my idea, but here it is..
What I was planning on doing was to generate a layer of rendered clouds (either the standard photoshop ones, or with the eyecandy Little Fluffy Clouds). Pop back to the land layer, make a selection, feather out to 100 and expand same. Use that selection on the cloud layer (likely invert the selection then delete everything else). From there it gets a bit fuzzier.. I think at that point, use the colour select to pick out all the black, or white, delete the appropriate one (maybe even do a layer of each for comparison to see what gives the best overall look) then run the woodcut effect on those layers, then overlay with the original woodcut outline and decide which one to keep.
As I say, I hadn't actually tried it so there may be some fine tuning needed, but that's the basic direction I was planning on.