Well, it is several months later, and I have called this little project done. I learned a lot, so let me summarize what I found.
* Some colors really are out of gamut with a particular paper and you will need to use a different (hopefully similar) color.
* Some papers (in this case a matte, natural book arts paper without any coating) have extremely limited color reproduction range when compared to inkjet photo papers. Profiling a paper/printer combo can't enable it to show every color.
* Using a tool like a colormunki, you CAN read a color and then try to reproduce it, but it looks unnatural. The world has noise. To make it look somewhat natural, I had to add noise (mostly luminance) to the reproduced image.
So here is what I finally ended up doing.
1) I took the scan I made of the "two color" original (paper color and deep brownish red ink color) and made a mask that I could reapply to a manually generated color background.
2) I used the colormunki to identify the RGB color values from the paper (there was a range of about six shades of color)
3) I used that color to fill a layer and then I used the mask created from the scanned version in step 1 to delete the negative space, allowing the paper color to show through.
4) I profiled the book arts paper
5) I printed the image and it looked terrible. Not anywhere even close to the original.
6) After lots of adjustment layers and soft proofing and out of gamut warnings, I was at my wits end. I believed that the paper I was given to work with and the printer I had could not reproduce that shade. I was right. I had been too hard-headed to see what the profiling software was telling me.
7) I added noise, mostly luminance, but some chroma noise too. this helped immensely. Because my created shade was all one digitally defined color, and that was out of gamut, I effectively had no pixels to work on to try to get it to look better. (Is there a way to add noise and to specify the RGB color values you want as, sort-of, seed values for the chroma noise?)
I got close, but not very close. The uncoated, natural, matte paper just couldn't handle reds very well.
What did I learn:
I think this project taught me a lot more about photographic color management than any photo could ever teach. In most photos if you used a canned profile, out of gamut colors are rare. The visual effect is generally subtle, often manifesting itself as a bit of posterization where certain colors are left out of the scene or clumsily overlayed by the printer. I have mostly seen this in highly saturated yellows and oranges. A minor desaturation of the offending color is usually enough.
As a photographer you have so few instances where you have to deal with major limitations, you kind of don't ever really get the significance of all the things you do in color management. In this example, PhotoShop's soft proofing capability was really amazing. It's show paper color function was spot-on. The out of gamut warning was everpresent, and because of the limitations of the paper, I was dealing with it constantly. With decent photographic paper, the paper doesn't dramatically diminish the gamut available to you. I find that soft proofing photo paper profiles to be of limited value, but with this paper soft proofing was extremely valuable.
Everyone should try this exercise. Get some crappy paper and try to duplicate something from the real world. It is an eye-opening experience.