The default gateway port in the Tableau Server configuration window needs to be left at port 80, if you set it to 443 Tableau Server won't be able to use 443 for SSL because it will conflict with itself.
I'd try creating a new cert and key from scratch without the password, using the article here:
On default gateway: sort of got that afterwards.
You are correct, after generating a self-signed certificate with a new key I was able to properly configure SSL for Tableau. It seems that certificate we got was either bad or maybe even expired.
Many thanks, it was the next step on my list - should have tried it sooner.