度々すいません、こちらも私の勘違いでした。
\usepackage[newparttoc]{titlesec}
と、newparttocオプションを付けただけで
第I部その1
となるのかと思ってしまいました。
\usepackage{titletoc}
\titlecontents{part}[0pt]{}{第\thecontentslabel 部\quad}{}{\hfill\contentspage}
というような、titletoc.styを使った指定も必要なんですね。
私が最初に示した例では入っていたものが、いろいろ試すうちに抜け落ちてしまったようで、私のミスです。
以上、お騒がせいたしました。ありがとうございました。