Convert to BW by replacing colors with “shapes” (for printing)

Using GIMP, you could:

• fill layers with your black & white patterns (one layer per pattern), and then
• use colour selection (Shift+O), select all the zones of one colour by clicking on it, and
• use that selection as a mask on the corresponding pattern layer (right-click → add mask to layer → initialise with “selection”), or alternatively invert the selection, select the pattern layer and delete.

The process is a bit manual but should be fairly quick for a simple map like this. If there is some anti-aliasing on the edges of the zones, either increase the size of the selection a bit (selection → grow) or increase the tolerance of the colour selection (in the tool’s configuration, below the toolbox).

You could in principle automate it to some extent via script-fu, if you’re willing to put in a few hours of programming.

• Open your colour image in GIMP
• At this point, you may want to “posterize” the image, to reduce the number of colours it contains, so that the selection is not as affected by anti-aliasing issues (pixels on the border of two zones which are not exactly of the colour of one nor of the other). An image with a higher quality (higher resolution / originally saved in a lossless format like PNG instead of a lossy format like JPEG) would give you better results, too. To posterize the image, use the menu Color → Posterize, and adjust the number of colours until you have an acceptable result. I didn’t think about using this in the screenshots below, but it will definitely help.
  
• Open your b&w legend in GIMP
• Copy the whole b&w legend (Ctrl+A, Ctrl+C), close that window
• Paste the b&w legend onto the colour image (Ctrl+V), and click the “New layer” button (step 1)
• Use the selection tool (step 2) to select the small square in the legend (step 4). Zoom in if you need precision (step 3)
  
• In the “Patterns” tab, select the “clipboard” pattern, showing what you just copied
  
• Deselect all (Ctrl+Shift+A or Selection → None)
• Select the bucket fill tool (step 1)
• Select “fill with pattern” in the tool options (step 2)
• Create a new layer in the “Layers” tab (step 3)
• Fill the whole layer with the pattern by clicking in the middle of the image (step 4)
  
• Hide the patterned layer by clicking on the “eye” icon next to it in the “Layers” window (setp 1)
• Also hide the b&w layer, for good measure
• Pick the “Selection by colour” tool (step 2), choose its threshold (step 3, the threshold 54 worked well for the “midlands” zone, because it has both light grey and dark grey, for the others use smaller thresholds and/or select multiple times, combining the selections with “shift”)
• Click the grey square in the legend to select all grey zones (step 4)
• The “Selection by colour” was a bit too greedy and selected some of the anti-aliasing around the text. Pick the rectangle selection tool (step 5) and Ctrl+drag across the text in the legend to deselect that part, to clean up (step 6)
• Alternatively, you can use the “magic wand” tool (fourth tool in the top row of the toolbar on the screenshot below). It works like the “selection by colour” tool, except that it only selects contiguous pixels of the same colour, instead of selecting pixels with that colour all over the place. By combining the selection (using shift+click), you can still select multiple zones with that tool. If you posterized your image a bit too much, and there are some colours which were supposed to be separate but got reduced into a single colour, the “magic wand” tool will help you select only the zones you want (or, use the “selection by colour” and de-select with the “rectangle selection” the parts you don’t want, as explained int the points above).
  
• To review what you have selected, you can click the “rapid mask” button in the lower left corner to see the unselected part in a red semi-transparent overlay; the selected part will be clear. You can edit the selection on-the-fly in this mode using the paintbrush, and painting white to select, black to deselect. Click the “rapid mask” button again to turn it off.
  
• Show again the patterned layer by clicking the empty spot where the eye would be left to its name in the “Layers” tab (step 1)
• Right click the layer name (step 2), and choose “add mask” (step 3)
• Choose “Initialize the mask to:” “Selection” in the dialog box that appears (step 4)
• Click the “Add” button (step 5)
  
• Deselect all (Ctrl+Shift+A), and admire the result
• 
• Lather, rince, repeat.

Strictly speaking, you could manage without using one separate layer per pattern, but I think it will make it easier to fix mistakes later on. For example, the mask appears as a second miniature rectangle next to the layer name. By left-clicking on it, you get to edit the mask (instead of the layer itself, which contains the pattern). By Ctrl+Alt+Clicking on it, you get to see the mask itself, and the same command reverts back to showing the masked layer.