The first two things I would check:
1. Is this server in the list of servers that you have distributed this run-as account credential to? It sounds like it could have been pushed to some servers but this one didn't get the credential. This would be found under the "Distribution"
section of the User account.
2. On the SQL server in question - check the security and application logs - is there an event showing failed authentication to the SQL server? Does the ID there match the expected RunAs account you've configured?
These two steps would verify proper setup - showing that the expected account is the one being attempted. If that all checks out, then you'll need to dive into the required permissions outlined in the MP guide.