This might seem like a silly question...when you add a contact on blackberry messenger...is it possible for the request to remain as pending if the other person does not accept your invite???
If the contact tells you they accepted you and it's still showing the "Pending" notification, remove the battery while the device is ON, wait a minute and replace. It should go through...