I second (or third, or whatever) the "decorate with stone" idea.
Also, how about different *natural* quality levels for specific stones/gemstones, determined when they're actually exposed to the air by a miner?
Maybe a randomization of value, based on the current value levels, but ranging from say 10% to 250% of those, so that a given emerald might be worth anywhere from x4 to x100, with an average of 40?
There might even be a little additional description to indicate how crummy or how choice that specific stone is.
Along with that, having gems range in carat-size *before* the gem-cutters get their hands on them, as well as after, would also be nice.
(The increases in size involved wouldn't normally be great enough to allow you to, say, build a throne out of emerald, but certainly emeralds that large *have* been discovered, so it's not an impossibility, just very unlikely. Maybe size could be more or less open-ended, with extraordinarily large gems of *any* kind being extremely rare. Quality increases in value might also be much rarer, as gem size increases, with very large gems typically being of low quality, with extremely large, high-quality gems again being almost impossible to find.)
Gem-cutters might then be able to cut those gems, with a loss in size/weight based on their skill level, and we might also see more than one cut gem coming out of a single uncut stone (with the possibility for us to be able to indicate and order what sizes and specific cuts of gem we'd like to have, limited by the skills of the gem-cutters available to us.).
You could then find a very large, but very poor quality emerald that was worth double the normal value due to it's size, but only worth 10% of the normal value due to it's quality, giving you a stone with a value of x8 (20% of average value.).
That emerald could then perhaps be cut into 2 large gems that would each have a value of 80, or maybe one huge gem (if your gem-cutter was up to the task) that would be worth 160, or possibly even more, if bigger and bigger cut gems were given a higher value (which would make sense)--and which would require higher and higher skill levels.
Stones like jet etc. could fall under the same system, with large, high quality stones commanding a greater value.
If jet has a value of say 2, an especially fine piece might be worth as much as 250%, or 5. With a size increase, that might reach up to, say, 10 or even 20, giving it the same value as many "ordinary" gems.