Caller id name is a separate service called CNAM [1]. It's handled by the terminating (reviving) carrier, and from my understanding, has been done using a mess of different database [2] and interchange formats (think: massive CSV versions of phone book, adhoc shipped between all different ILEC/CLECs). The cellular carriers never got into publicly listing phone numbers for whatever reason, so there's generally no names available for outgoing calls. Your carrier also has to actually provide this service to you for incoming calls, and it seems like most don't, which I'm guessing is them trying to save money as the standards (GSM, CDMA, etc) all seem to support it. Apparently some carriers offer it for an extra fee.
[1] https://en.m.wikipedia.org/wiki/Calling_Name_Presentation
[2] https://en.m.wikipedia.org/wiki/Line_information_database