With BB Messenger, you can't just add a contact. You have to send a request to them to be a contact. Click on "Add a Contact", scroll to the contact you want to add, click it, and you should get a prompt to send it to their email. They'll get the message, and either approve or disapprove.
Does the person you're trying to add have 1) a BlackBerry (you need a PIN number), and 2) an email address in the record?