No worries, you'll kick yourself though because it's quite elegantly simple.
I'm very sorry, but I'm still not getting it :/
Not quite, but the best possible path from every enemy to every friendly isn't what you need. What you need is the best path for each enemy to its nearest friendly (and viceversa) and that can be done with just two search one for each type to generate your walkmaps.
Let's say I have 100 enemies and 100 friendlies.
You're telling me that I can find the best possible path from every enemy to every friendly (and viceversa) with only two breadth-first searches?
Each cell in the walkmap represents the distance from that cell to an entity, so a unit sitting on that cell should examine the surrounding cells and pick one that is lower (and/or perhaps equal) to the value of the cell it is sat on.
As you know a breadth-first search is based on a queue, you enqueue stuff to the back and dequeue stuff from the front.
Where do I have to start the searches at?
To start the search you seed your queue with the cells of all entities (let's say all enemies) and mark them with a distance of 0.
Pop a cell off the front of the queue, add its surrounding neighbour cells to the back of the queue and mark each neighbour with a distance of 1+ whatever the central cell is marked as (e.g. 0+1 = 1), if you come across any neighbour cells that are already marked with a value then leave them alone (don't enqueue and don't change their value).
Loop until the queue is exhausted.