Have you tried going to the Firefox Account settings from the Firefox settings page (about:preferences), clicking the Disconnect... button and then reconnecting your Firefox Account?

Yes, and unfortunately it does not do the trick.

I've tried that approach a number of times.

Should I try reinstalling Firefox?

I don't see many other options I can try from my side.

It would not hurt to try and reinstall Firefox, since it's possible that you have a damaged file. However, I don't think it will fix the issue because it sounds like the issue is more with the Firefox profile folder on your computer, which will stay on your computer even if you reinstall Firefox.

Nevertheless, give it a try and see if it works.

In case of issues with Sync you can try this:

Disconnect from Sync and Reconnect to Sync again. You can disconnect from Sync by clicking the e-mail address in the "3-bar" Firefox menu button drop-down list or go to "Options/Preferences > Sync". Delete the signedInUser.json file in the Firefox profile folder and delete the Weave folder (Sync was formerly named Weave). Remove an existing chrome://FirefoxAccounts entry in the Firefox Password Manager. If that isn't enough then delete the prefs.js files to reset all prefs and maybe also delete the compatibility.ini file to reinitialize the profile.

You can use the button on the "Help -> Troubleshooting Information" (about:support) page to go to the current Firefox profile folder or use the about:profiles page.

• Help -> Troubleshooting Information -> Profile Directory:
  Windows: Show Folder; Linux: Open Directory; Mac: Show in Finder
• http://kb.mozillazine.org/Profile_folder_-_Firefox

I tried deleting each one of these files. I also uninstalled (without completely purging) Firefox, then reinstalling to no avail.

Try the Firefox version from the official Mozilla server if you currently use a version from the repositories of your Linux distribution.