What version of traveler are you running? I recommend 9.0.1, they also just released a new IF1 patch for it. Also, 9.0.1 added specific and native support for BlackBerry devices.
Are you using a BES 10.1 server between the devices and Traveler? This is still the recommended solution from BlackBerry.
If not, are you using any Traveler policies in your Domino Domain? I read that it is now recommended that you just use the default device policy in the traveler database on the traveler server. In that policy you will find settings that allow you to control how the devices work with the Traveler server. NOTE: If you have to delete / remove policies from your Domino Domain, you will need to run an AdminP command that removes the Traveler policies from the user's mail files. If they are still there, they will cause conflicts and issues. This I know from personal experience.
TL:DR - While you can use a BB device directly with Traveler, BB still recommends that you use a BES 10.1 or higher server for your BB devices. You also really need to make sure you are using Traveler 9.0.1 or higher. No Traveler policies in your Domino domain. Use the default device policy in the traveler database to control device settings.
Right now, where I work, we are using a BES 10.1 server connected with a Traveler 9.0.1 IF1 server in a separate but cross-certified Domino Domain. The Traveler server connects with our primary Domino Domain and uses directory assistance to lookup users, server addresses, and the like. With this setup we have seen no such issues with names in e-mail messages not showing up properly.