BB Messenger is a BB to BB message service, that uses the data network (unlike standard SMS text messages which use the voice network). It will work between your BB and any other BB, regardless of which carrier they are on. The addressing / routing is provided through the device PIN number and not the phone number.
The invite / accept process can sometimes be tricky. Be sure you are sending an invite to a specific PIN and not to an email address (which it will default to if you invite a contact in your address book that has an email address but no PIN entered). Your invite status will continue to show pending until both parties have accepted. If it continues to show pending, then you both should delete the contact and start the invite process over.