I know how to add by PIN, and for some reason, about half the time it won't add, and half the time, it works fine. They just sit in pending, and the other party will add me, and mine sits in pending there too.
Are you both sending a request to each other at the same time then trying to add each other at the same time? If this is the case I do not think it works like that. Try and send the request to your friend then have them accept it and you should be ok.
I have the same problem sometimes adding contacts. I added 5 people without a problem then the next one just doesn't show up. The last thing that worked was to make sure there were no requests and neither of you had the other shown in the contacts section. Then both do a battery pull and one of you send the request to add, the other will accept and then both will move to the contacts list from pending. For some reason this worked for me. Good Luck!!