hmmm, mthr, have you tried deleting both your contacts from each other's devices and all BBM conversations, as well. AND the PINs from each contacts Address Books if you have them there, also. Reboot and make certain neither remains in the contacts list.

THEN, one of you add the other back BY the PIN in BBM. Make sure you are both in the other's contact list, etc., and try again.

Worth a shot.