一般フォーラム

\mathchoice による「4 重分岐」では，その分岐先の 4 個の数式を「あらかじめすべて処理」したうえで記憶しておく
（そして，後から実際に用いられるスタイルに対応する処理結果をはめ込む），ということが原因です
（単純にいえば，「そういう仕様」ということです）．詳しくは『The TeXbook』等を参照してください．

もちろん，下のサンプルに示すような回避法はあります…… が，おそらく emath として知られるパッケージ群を用いたほうがお幸せになれるのかもしれません．

\documentclass{article}
%%% amsmath 不使用時
%\makeatletter
%\def\root#1\of{%
%  \setbox\rootbox\hbox{%
%      $\m@th\scriptscriptstyle{#1}$%
%      \@root@save@counters\expandafter}\@tempa
%  \mathpalette\r@@t}
%\def\r@@t#1#2{%
%  \setbox\z@\hbox{\@root@restore@counters $\m@th#1\sqrtsign{#2}$}%
%  \dimen@\ht\z@ \advance\dimen@-\dp\z@
%  \mkern5mu\raise.6\dimen@\copy\rootbox
%  \mkern-10mu\box\z@}
%\def\@root@save@counters{%
%  \def\@elt##1{%
%      \expandafter\ifx\csname c@##1\endcsname\c@page\else
%        \global\expandafter\noexpand\csname c@##1\endcsname
%                \number\csname c@##1\endcsname\relax
%      \fi}%
%  \edef\@tempa{\def\noexpand\@root@restore@counters{\cl@@ckpt}}}
%\makeatother

%%% amsmath 使用時
\usepackage{amsmath}
\makeatletter
\def\plainroot@#1\of#2{%
  \setbox\rootbox\hbox{%
      $\m@th\scriptscriptstyle{#1}$%
      \@root@save@counters\expandafter}\@tempa
  \mathchoice
      {\r@@t\displaystyle{#2}}%
      {\r@@t\textstyle{#2}}%
      {\r@@t\scriptstyle{#2}}%
      {\r@@t\scriptscriptstyle{#2}}%
  \egroup}
\def\r@@t#1#2{%
  \setboxz@h{\@root@restore@counters $\m@th#1\sqrtsign{#2}$}%
  \dimen@\ht\z@\advance\dimen@-\dp\z@
  \setbox\@ne\hbox{$\m@th#1\mskip\uproot@ mu$}%
  \advance\dimen@ by1.667\wd\@ne
  \mkern-\leftroot@ mu\mkern5mu\raise.6\dimen@\copy\rootbox
  \mkern-10mu\mkern\leftroot@ mu\boxz@}
\def\@root@save@counters{%
  \def\@elt##1{%
      \expandafter\ifx\csname c@##1\endcsname\c@page\else
        \global\expandafter\noexpand\csname c@##1\endcsname
                \number\csname c@##1\endcsname\relax
      \fi}%
  \edef\@tempa{\def\noexpand\@root@restore@counters{\cl@@ckpt}}}
\makeatother

%%% 実験用マクロ
\newcounter{foo}
\def\zzz{\fbox{\stepcounter{foo}\thefoo}}

\begin{document}
\section{サンプル}

$\sqrt[\uproot5 \zzz]{\zzz}$,
$\sqrt[\uproot5 \zzz]{\sqrt[\uproot5 \zzz]{\zzz}}$
and
\begin{gather}
  \sqrt{\zzz} = \sqrt[\uproot5 \zzz]{\zzz} \\
    \sqrt{\zzz\zzz}
  = \sqrt[\uproot5 \zzz]{\zzz\zzz}
\end{gather}
\end{document}

「その場しのぎ」でよければ，次の例のように「オプションつきの \sqrt の引数中では \stepcounter を
実行しないで済むようにあらかじめ文字列化したものを用意する」という方法でもどうにかなるでしょう．

\documentclass{article}
\usepackage{amsmath}

\newcounter{foo}

\begin{document}
\section{サンプル}

$\stepcounter{foo}\edef\tempA{\arabic{foo}}%
\stepcounter{foo}\edef\tempB{\arabic{foo}}%
\sqrt[\uproot5 \fbox{\tempA}]{\fbox{\tempB}}$,
$\stepcounter{foo}\edef\tempA{\arabic{foo}}%
\stepcounter{foo}\edef\tempB{\arabic{foo}}%
\stepcounter{foo}\edef\tempC{\arabic{foo}}%
\sqrt[\uproot5 \fbox{\tempA}]{\sqrt[\uproot5 \fbox{\tempB}]{\fbox{\tempC}}}$
and
\begin{gather}
  \sqrt{\fbox{\stepcounter{foo}\arabic{foo}}}
  =
  \stepcounter{foo}\edef\tempA{\arabic{foo}}%
  \stepcounter{foo}\edef\tempB{\arabic{foo}}%
  \sqrt[\uproot5 \fbox{\tempA}]{\fbox{\tempB}}
  \\
  \sqrt{\fbox{\stepcounter{foo}\arabic{foo}}
        \fbox{\stepcounter{foo}\arabic{foo}}}
  =
  \stepcounter{foo}\edef\tempA{\arabic{foo}}%
  \stepcounter{foo}\edef\tempB{\arabic{foo}}%
  \stepcounter{foo}\edef\tempC{\arabic{foo}}%
  \sqrt[\uproot5 \fbox{\tempA}]{\sqrt[\uproot5 \fbox{\tempB}]{\fbox{\tempC}}}
\end{gather}
\end{document}