You need to have the PIN number of the person you want to add as a contact.
Try this: add contacts using PIN, not EMAIL
Delete your pending requests. Tell the other parties to delete any pending requests from you.
In BBM, hit add contact. If they're not in your address book go up to use once. HOVERING (highlight, not click) on use once, hit the menu button and select request by PIN. Then just type in the PIN and send request. If they are in your address book, HOVER (highlight, not click) over their name, hit the menu key and send a request using PIN that way.
The contact must accept the request for it to be complete. Both devices must have data plans.