Looks like the solution is to use the != function, as described here: https://groups.google.com/forum/#!topic/minikanren/JCKJV7k7lGU

Turns out rembero is a core.logic function already as well, in case anyone is interested:

(defne rembero
  "A relation between l and o where x is removed from
   l exactly one time."
  [x l o]
  ([_ [x . xs] xs])
  ([_ [y . ys] [y . zs]]
     (!= y x)
     (rembero x ys zs)))