alien-nums.clj

(ns alien-nums
  (:require (clojure.contrib [combinatorics :as comb :only cartesian-product]
			     [seq-utils :as seq-utils :only indexed])))

(defn leading-zero? [lang num] 
  (= (first num) (first lang)))
  
(defn generate-nums [lang]
  (when-let [lst (map list lang)]
    (let [fcp #(map flatten
		   (comb/cartesian-product lst %1))]
      (remove #(leading-zero? lang %)
	      (apply concat (iterate fcp lst))))))

(defn get-index [nums num]
  (first (some #(when (= (second %) (seq num)) %)
	       (seq-utils/indexed nums))))

(defn valid-num [lang num]
  (and (every? (set lang) num)
       (not (leading-zero? lang num))))

(defn convert-num [alien-num from-lang to-lang]
  (let [[from-nums to-nums]
	(map generate-nums [from-lang to-lang])
	idx (when (valid-num from-lang alien-num)
	      (get-index from-nums alien-num))]
    (when idx (apply str (nth to-nums idx)))))

I have to think deeply in your recursive solution which is more efficient (nearly constant time!), mine is horribly slow, at least O(n) cause it walk (with some and nth) each seq of nums until reach the solution . I'll try to combine them is some way