There are a couple of places within the 5000 where outbound caller ID (called CALLING PARTY NUMBER and CALLING PARTY NAME) are specified. On is within programming of each phone (if you fix one, use copy/paste to fix all the others). The other place is within CO TRUNK GROUPS. Rarely have I seen a carrier actually let us specify a CALLING PARTY NAME, but I understand it's possible. Anyway, check these fields. If no name/number is specified for the phone it uses the trunk group name/number. If none is specified for the trunk group it uses the carrier record for the PRI. Ultimately I'm betting that since the number originally belonged to someone else (owner of the PRI) that is still the name-of-record associated with that number and will have to be changed by the controlling carrier. Test is to make sure all those fields are blank in the 5000, make a call. If you see the right number but not the name you want, it's on the carrier! You can try to over-ride by putting a name in the CO TRUNK GROUP but I'm not optimistic the carrier will pay any attention to it.
Fun experiment: if you put YOUR home phone number in the CALLING PARTY NUMBER field, bet you'll see your home number and home billing name on caller ID, it's getting the name through looking up the number. All these name/number relationships are in gigantic tables at each carrier. Note that if this is a recent change for this customer it sometimes takes quite a while to roll the change out to all the carriers (lookup appears to take place at the receiving end).