How to delete an element from a nested list?

My guess is that you're using vectors as sequences.

(eliminate 3 [3 3])
;()

(eliminate 3 [3 [3]])
;([3])

This would have been trivial to find had you shown us an example: tut, tut!

What's going on?

Although vectors are seqable, they are not sequences:

(seq? [])
;false

At the outer level, you treat lst as a sequence, so first and rest work, since they wrap their argument in an implicit seq. But seq? will fail on any immediately enclosed vector, and those further in won't even be seen.

If you replace seq? with sequential?, lists and vectors will work.

(sequential? [])
;true

More serious, as @noisesmith noted, is your use of def and defn at inner scope. Replace them with let or letfn.

You could also improve your style:

1. Replace (if-not (empty? lst) ... ) with (if (seq lst) ...).
2. Use cond to flatten your nested ifs. This requires inverting the test in (1), so removes the need for it.
3. Use recur for the tail-recursive case where you find value, as @Mark does.

If you don't want to see the result, look away now:

(defn eliminate [value lst]
  (letfn [(sub-eliminate [lst]
            (let [current-item (first lst)]
              (cond
               (empty? lst) '()
               (sequential? current-item) (cons (sub-eliminate current-item) 
                                                (sub-eliminate (rest lst)))
               (= value current-item) (recur (rest lst))
               :else (cons current-item (sub-eliminate (rest lst))))))]
    (sub-eliminate lst)))

There is a remaining tender spot:

• You invoke (first lst) before you know that lst is not empty. No harm done: you'll just get nil, which you ignore.

An Alternative Apporach using Destructuring

You can often use destructuring to abbreviate recursive processing of sequences. I'd be inclined to express your function thus:

(defn eliminate [x xs]
  ((fn rem-x [xs]
     (if-let [[y & ys] (seq xs)]
       (if (= x y)
         (recur ys)
         (cons
          (if (sequential? y) (rem-x y) y)
          (rem-x ys)))
       ()))
   xs))

For the sake of learning take a look at this function:

(define rember*
  (lambda (x l)
    (cond ((null? l) '())
          ((atom? (car l))
          (if (eq? (car l) x)
              (rember* x (cdr l))
              (cons (car l)
                    (rember* x (cdr l)))))
          (else (cons (rember* x (car l))
                      (rember* x (cdr l)))))))

This is a simple recursive function from book 'The Little Schemer', which is a good source to learn how to write such recursive functions.

Let's see if we can translate it into Clojure:

(defn rember* [x l]
  (cond (empty? l) '()
        (seq? (first l)) (cons (rember* x (first l))
                               (rember* x (rest l)))
        :else (if (= (first l) x)
                (recur x (rest l))
                (cons (first l)
                      (rember* x (rest l))))))

user> (rember* 'x '((x y) x (z (((((x))))))))
;; => ((y) (z ((((()))))))

(defn expel [victim xs] 
  (mapcat (fn [x]
            (cond
              (sequential? x) [(expel victim x)]
              (= x victim) [] 
              :else [x])) 
          xs))