Can you try these steps:
1. From the Server Menu -> Sign In option -> Sign out (not from the workbook's bottom sign-out)
2. From the Server Menu -> Sign In -> type the website as: https://public.tableau.com/
If it does not ask for your credentials, which happens mostly when sign-out and sign-in immediately back, then make sure you sign-out again as in step 1.
(This is the most important step which I noticed during my ordeal for around 3 hours)
3. Provide your credentials again to sign-in
4. Now Save the workbook either using Server -> Tableau Public -> Save to or Save As option.
Yay! It worked! I had to retry the steps for a few times, though. Thanks a lot!