I am getting this error in my sys.transmission_queue table whenever I attempt to send a SQL Service Broker message between two different SQL Server servers. (i.e. the databases are on two different physical machines)

Dialog security is unavailable for this conversation because there is no security 
certificate bound to the database principal (Id: 5).  
Either create a certificate for the principal, or specify ENCRYPTION = OFF 
when beginning the conversation 

When this error refers to "database principal" what is it referring to? (the "master" database? dbo user?) I've used the CREATE CERTIFICATE command, backed up the certificate and created a same named certificate on the other server with the backup .cer file from the first server, but I keep getting this message.

Any help would be appreciated in getting me pointed in the right direction. I must be missing something obvious.

FYI, in my development environment, both the initiating and target databases were on the same physical server, and same SQL instance, and everything was working fine.