I had this problem... and this is how you do it I believe.
Go to 'Add a Contact', scroll up to [Use Once] and press the menu button (blackberry button), then choose 'Request by PIN' and it should then let you type in the PIN number.
I tried adding by just choosing [Use Once] but it would still add them as e-mail.
If you have their PIN, go to your address book and click on their contact info and edit..then there is a place for 'PIN' like phone #s/e-mail/addy etc. and save.
After all that, go to BB messenger -> menu -> 'add a contact...' -> click on the person u want to add