はじめに

うまくいかないパターン

% git fetch
remote: Invalid username or password.
fatal: Authentication failed for （略)

ほとんどの人は以下のURLで解消すると思います。
https://qiita.com/gin_teacher/items/d52a25fb5ca9fed3108a

似たような記事もいくつか参照しました。
https://zenn.dev/yuri0427/articles/9587ae6a578ee9
※ "git push origin"は流石にアレなので基本的には"git fetch"のほうがいいと思う

キーチェーンをクリア（または更新する）
git config -global で要素を更新する

普通はこのあたりを実施することで再度権利情報（usernameとかpasswordの確認）確認が登場して、そこで新しいトークンをパスワードとして入れればいいと思います。

自分の場合ここで何をやっても解消せず、キーチェーン以外の各所のキャッシュクリアなどを経てもまだ再更新されない状態になったので、解消のための確認を一応メモがてら残しておこうかと。

確認したほうがいい点

% git remote -v

結果の例

% git remote -v 
origin  git:{古いトークン}@github.com/hoge.git (fetch)
origin  git:{古いトークン}@github.com/hoge.git (push)

みたいに、remote時点でトークンが埋まっていることがある。何故か自分がそうだった。
※GitHub　EnterpriseのURLを差し替えて書いたため、名前やトークンの位置は異なるかもしれない。

もちろん新しいトークンに差し替えても動くが、次回更新時に再度引っかかるので、パスからトークンを除去しておくのが正解かと思われる。

手元で２パターンをCLI（ターミナル）とInterlliJから試したが、どちらも以下のように成功した。

新トークンを入れた場合、そのまま処理成功
トークン部（コロンも）を除去した場合、権利情報入力が出てきたので、ここで新トークンを入れたあと処理成功

確認経緯

キーチェーンをクリアしても駄目（権利情報確認なしに接続不可）だったので、最初はInterlliJのキャッシュや接続情報が古くて出ないのだと思っていたが、ココをいくら飛ばして再設定しても出てこない（GitHubでトークンを再設定するのをInterlliJ経由でやっても不可）。
念のためCLIで打ったが状況が変わらない。

PCそのものを再起動しても駄目で、念のため１晩おいたが当然状況変わらず。

一晩おいたことで冷静になったので、ファイルを退避して再度リポジトリを掘り直してみようと思い、"git remote -v"で今の設定URLを確認。

あれ？このURLトークン埋まってない？多分古いっぽいから新しいトークンに差し替えよう→動いた。

流石にトークン埋めてると次の更新でまたややこしいから除去しておいたほうがいいかな→権利情報確認出た。

最後に

行き詰まったらお茶飲んだりでリフレッシュして「ココは大丈夫」の思い込みを減らしたり、切り分けられそうな原因を少しでも気づく限りほっていくほうがいいっすね。
最初の設定時になんでトークンが埋まったのかは謎でしたが、思い返してもしょうがないので仕事に戻ります。

万一別の誰かが同じことで引っかかった際には自分みたいに半日飛ばさずこの記事にたどり着けますように。