You might want to try this step-by-step… This helped me resolve the issue, even without uninstalling the Uphold app before verifying as other solutions have suggested. Here it goes, as below:
STEP 1: Go to your Brave Rewards section. I hope you see something like this…
Action: Tap on the “Unverified” drop-down…
STEP 2: You should see something like this…
Action: Tap on “Continue”
STEP 3: Now you will see this…
Action: Select Uphold
STEP 4: Once you select Uphold, it will show this…
Action: Tap on “Continue to login”
STEP 5: If you already have a Uphold app installed on your Android, it will give you a choice to open “Continue to login” (from previous) in either Uphold app or Brave or any other browser (depending on what you have installed on your Android device).
Action: Select Open With —> Brave —> Just Once
STEP 6: It will take you to a browser login version of Uphold.
Action: Do the login and 2FA through Google Authenticate or whatever other mechanism you have…
Once you do all this, Uphold will log in your account and automatically re-direct you to the initial Brave Rewards setting screen (as shown in Step 1), where you will see something like this…
Here you will see your wallet verified…
This worked for me, despite having Uphold app already installed on my Android device! Hope this helps you too… 