as you live in "somewhere with a piece of paper in my hand" it may be hard to give you a good helping hand. in Germany that kind of coloured kraft paper is also often sold as bookwrapping paper. I bought it for a couple of years because the have been some really nice colours. it was always around school enrollment when the shops sold that kinf of paper (for the kids to protect their expensive school-books).
maybe you can search for bookwrapping paper in "somewhere with a piece of paper in my hand".
Orislater - just to point this out, you spelled "wrap" "rap." It's not that difficult to add a "w" to the front of the word. Once again, spellcheck!! I don't live in Idaho, so I can't really say, but there are most likely some places to get it on the internet. I got a paper from Joanne's art supply store, but I can't remember what it was called (it was by the tracing paper). It has a texture similar to very thin wrapping paper, and is great for folding - you could use that instead, if you live by a Joanne's.
In the UK you can get coloured kraft paper. The paper I've seen is coloured on one side.
It's not origami specific, and comes on a roll. I'd check out trade paper or packaging retailers. I wouldn't be at all surprised if you find some. It should be fairly cheap too.