As justinsm2 suggests, I'd start with the Telco. The real question I'd ask is whether a valid number is being sent with the calls? Is it always the same number? If so, have the Telco check the LIDB database name for that number. It could be set to "unknown name". It could also be set to private number, which the Telco can control. If a number is not showing up, then you either need to send a 10 digit DN, or the Telco needs to put in a default number if you don't send it.
As for sending your own name from the PBX, I've run into problems with some terminating CO's rejecting calls where the name is sent from the PBX rather than from a LIDB lookup.