Just find a bottle of india ink (at a hobby store, craft store, etc.), "paint" the paper with the ink, and let it dry. Then cut to size due to the paper changing from the liquid. India ink comes in a variety of colours (including black) that you can mix together to get other colours you want/need.
That's what I've been doing for most of my kraft and tissue paper. I don't know if this will help you now, but I just thought it would be something nice to know.
