Try using a good amount of Northern Brewer hops for flavor and bittering. That's the key for a nice, herbal spiciness.
The use about 20-25% rye in the mash, and definitely add some rice hulls to avoid clogging.
We use some dark crystals to round out the grain bill, and a base mostly of Maris Otter 2-row pale malt. Add a pinch of Chocolate and you got yourself a Righteous Rye.
I asked a couple of follow-up questions, and he added:
I recommend using a nice clean neutral yeast like 007 from white labs. A good pinch of chocolate rye wouldn't hurt either. For dark crystal matls, 120L is perfect and highly recommended