Certificate Private Key Cannot Be Found

I set up Service broker (2008R2 -> 2012) across different servers and domains using certificates.I set up 2 queues (one for sending, one for receiving).I set up 6 services (3 for send, 3 for receive), all 3 sharing the same queue type. (srv_send_1, srv_send_2, srv_send_3), (srv_receive_1, srv_receive_2, srv_receive_3).I set up a route for each receiving service on the source, and for each sending service on the target.I set up a SB binding to the remote for each sender service type.I granted send rights to the sending services on the source server.

I then tested my first service, and it worked perfectly (still works).My second service however is failing with the error "The certificate's private key cannot be found".I am stumped, as all the setup code was a lot of copy/paste which I have checked, rechecked and even re-coded.Basically, here is what Im doing:

begin dialog @ConversationHandle
FROM Service srv_send_1
TO Service 'srv_receive_1'
ON CONTRACT myContract
WITH ENCRYPTION = OFF, LIFETIME = 60*60*24*7;
SEND ON CONVERSATION @conversationHandle
MESSAGE TYPE [my_msgtype] (@xml);

The above code works 100% with service1, but not with service2.Note that on profiler, the target server doesnt receive any communication. The error shows on the sender profiler.Also, The conversation shows up as CONVERSING in sys.conversation_endpoints and the entry exists in sys.transmission_queue.