\mathrel conflict with \left,\right,\middle

No space is inserted in script or scriptscript styles if you precede \; with \nonscript:

\DeclarePairedDelimiterX\setnew[2]{\{}{\}}{%
  #1 \mathclose{}\nonscript\;\delimsize|\nonscript\;\mathopen{} #2%
}

Another solution that avoids \nonscript is

\DeclarePairedDelimiterX\set[2]{\{}{\}}
  {#1 \mathrel{}\mathclose{}\delimsize|\mathopen{}\mathrel{} #2}

If you are comfortable in using the alternative spacing you suggest:

\DeclarePairedDelimiterX\setnew[2]{\{}{\}}{#1 \;\delimsize|\; #2}

rather than

\DeclarePairedDelimiterX\set[2]{\{}{\}}{#1 \mathrel{\delimsize|} #2}

then try adding

\usepackage{etex}

in your document preamble. \middle is part of an etex extension.