i'm having the same problems lately too. a friend of mine just picked up a new bb on a different network. he's having no issues adding any of our friends who also use bb messenger, but i'm not able to add anybody on my 8120.
also, i've noticed that on the 8120 and any other device using 4.3 it only lets you add via email and not PIN. anyone else notice this as well?