I need to exclude from a query a category and a few custom taxonomies

Change 'relation' => 'OR' to 'relation' => 'AND' to apply both exclusions to all posts returned. It may seem counterintuitive, but a post that satisfies one of the exclusions will be included even if it doesn’t satisfy the other.

EDIT

From the code linked in your comment below, this is the query being generated:

SELECT SQL_CALC_FOUND_ROWS duk_posts.ID
FROM duk_posts
WHERE 1=1 AND 0 = 1
AND duk_posts.post_type="post"
AND (duk_posts.post_status="publish"
OR duk_posts.post_status="private")
GROUP BY duk_posts.ID
ORDER BY duk_posts.post_date
DESC LIMIT 0, 10

as you can see, there’s nothing related to category or taxonomy there, and the WHERE clause is an invalid condition that could never be true. This leads me to believe that your custom taxonomy is not being registered correctly, so when the query is run it is seen as an invalid taxonomy and therefore creates this invalid query. I’ll guess you register the taxonomy on the wrong hook or somehow have the name wrong.