This is your issue. Doing a fresh install is starting off like you never used Brave or Brave Rewards before. And since Gemini is unavailable, you wouldn’t be able to connect. The only way you’d have kept the connection is if you used your existing Rewards profile.
If you look at https://support.brave.com/hc/en-us/articles/6539887971469 you’ll see Gemini is only available for Creators only at this time. And even then, it’s just for the United States.
TL:DR = Installing brand new means you can’t connect. Gemini is not available. You will need to use Uphold or otherwise wait until either Gemini comes back or Brave starts on chain payments.