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)))