Should I reformat the time capsule with disk utility?
It is not possible to erase / format the Time Capsule drive using Disk Utility. You would use AirPort Utility as I detailed above.
If the Quick Erase has completed correctly, then you can proceed. However, I would recommend that you use the Zero Out Data option for a much better quality erase, especially if you are now running Big Sur or Monterey on your Mac.
When the erase procedure has completed.......
Click on the Time Machine "clock" icon at the top of the Mac's screen
Click on Open Time Machine Preferences
Remove the current drive.....named "Data" unless you have renamed the hard drive on the Time Capsule
Close the windows
Power off the Time Capsule
Restart your Mac
Power the Time Capsule back up
Open up Time Machine Preferences again and select the Time Capsule's hard drive
You have see a message that the hard drive has changed......(it has). Click to allow Time Machine to use the newly erased Time Capsule hard drive
Wait to see if Time Machine will start a new backup. You may see "Preparing" for a long time, because Time Machine has to take a slow look at all of the data on your Mac's hard drive....before.....the actual backup can begin. Let "Preparing" run until the backup completes or until you see an error message.
If an error message appears, post back with the exact text of the message.