A Publishing Request is the command for a specific family tree to be published to a specific site.
In order to publish a family tree you must create a Publishing Request.
A Publishing Request can be made once and then reused.
If I opened a publishing request for site X on account X and then changed the account details to account Y, the publishing request I currently have open would become invalid and would give the error message.
Family Tree Builder only knows that in Account X exist Site A, B and C and in Account Y exist Site 1, 2 and 3. When you get the "Site does not exist" error it is because you are esentially telling FTB "on account Y, publish to site A". For FTB there is no such thing.
It's okay to have "account Y, site 1" or "account X, site A".
It is not okay to have "account Y, site A" or "account X, site 1".
If you want to publish to a site that is on a different account, you should go to Publishing > My Sites and log in with the details of your second account. Then go back to Publishing > Publishing Settings and "use this account" and again enter the secondary account details.
Now all the relevant publishing requests for that specific account will be retreived and you will be able to successfully publish.