tax_query does not work with pagination with custom query (both wp_query and query_posts())

The issue isn’t the tax_query, but rather the offset. Offset and pagination do not play nicely together:

offset (int) – number of post to displace or pass over. Warning: Setting the offset parameter overrides/ignores the paged parameter and breaks pagination

The Codex has a somewhat involved workaround.