You mentioned local outlets, but visit your local fabric stores and see what's in stock. You would be surprised what you can find. I had a couple of FabArm Emebbi cases with dark blue velvet lining (looked like a gangsters coffin) and found a near-exact match at a local place that does drapery.
You mentioned a dark, olive green color. If you find the right texture of felt in the more typical bright green, try darkening it with a soak in black coffee. It will probably shrink as it dries, so cut the felt after you get the color you want.
