You need their PIN #. Ask them to go to options>status>pin #. Add the PIN to your address book under their name. Then go to BB Messenger and "add to contact" via PIN. It will give you the option to add them via "PIN" or "email" if you have this in your address book.
Good luck, works great.