I was working on setting up a Service Broker between two database instances and run into the above error. I noticed that the error happen only if the two database instances is on the same database server. Then I recalled what I did when setting up the conversation between two databases on separate instances on a two different server. I copied the certificate from the initiator database server to the target server and the certificate from the target to the initiator database server.
The solution to the dilemma is move the certificate created by the initiator and target to a different folder before Create references to target and initiator objects. For instance, when creating the target certificate, if you backup location is N:’C:\cert\ InstTargetCertificate.cer’; Move the certificate to a different folder location before creating references to target objects.
To learn more on how to Completing a Conversation between Instances https://technet.microsoft.com/en-us/library/bb839483%28v=sql.105%29.aspx