This can probably be done in some ways in illustrator but it will probably involve a lot of works like you already find out.
You can probably save some time trying to do this in Photoshop and with the help of Andromedia Cutline filter ( http://www.andromeda.com/main/cutline.php ). Than bring back to Illustrator to add color with live pain or even also finish it in Photoshop. All depend if you want the end results to be vector of not.
Good luck and share your finding!
Than bring back to Illustrator to add color with live pain
Now we are getting serious, Jean-Claude.
Undoubtedly, the added colour is red.
Illy does have some tools to bring it out in the open.
Speaking of which, it is more than half an hour after midnight over here, so some of us shall have to attend to other duties.