Hey Rets,
Sorry nobody ever posted a reply - now it's 17 months later and you've probably given up all hope! I signed up because of the exact same reason as you. My doc put me on a gluten-free diet last winter. Long story short, my best success has been with malted millet; it more-or-less has replaced barley as my base malt.
For some reason it's not the easiest to find. In my area it grows readily so you come across it at markets and such (people do everything for themselves in the West) but that's not a very reliable source. I've seen it online sporadically. If you're still looking for more info, give me a holler and I'll tell you what I know.