Hey Mark -
Sorry - I've run into this myself once, and it was a frustrating experience. The good news is the fine folks at Tableau Support have a series of steps that they can run you through to get this sorted out. If I were you, I'd open a support case.
If necessary, download and install the Eval of Tableau Desktop (which uses the same licensing bits), too. I suspect you'll see the same error there. If you get the "licensing stuff" sorted for the eval, it should be sorted for Public, too.