I think BB Messenger uses peer-to-peer for message transport, so it would be the same as if you sent a PIN. If PIN doesn't work between you and a give individual (or network) BB Messenger won't work.
I'm glad I'm not the only person that had this problem.
My I.T. department was of no help. I sent them a detailed E-mail which said many things, including (and I quote): We both successfully did a "Regenerate Encryption Key", but that did not fix it.
The E-mail I got back from them was, "You need to regenerate the encryption key." Followed by instructions on how to do it.
I, of course, wrote them back saying, "Did you even read my first E-mail?" Their reply was, "Sorry, we don't know. We suggest regenerating your encryption key." Argh!