1. Do you have a data plan? No data plan, no BB messenger. On both sides.
2. Are you adding your friends by their Blackberry PIN number? The BB messenger is only for communication between Blackberry devices and only by using each Blackberry's unique PIN number.
3. What does the message you got back say?