Switch to T-mobile, buy a compatible device, and pay the extra $4 a month to get it?

By the way, Caller ID is the display of the number, which you have. Displaying the name is in addition to that.

The name is not passed as part of the caller ID for landlines from the calling phone network. Your phone company subscribes to some service that looks it up when the call comes in if it's not one of their numbers, passes that back to the phone company, and displays it on your phone. They pay per lookup for the information. For example, tmobile uses Cequint to provide the info for their users.

Because the vast majority of calls received by cell phones are from people already in your directory or assumed to be known to you (after all they have your number), the wireless carriers did not have the incentive or the demand to spend the money to provide the caller name. If the other carriers thought there was a market for it, they would have followed Tmobile and rolled it out for a monthly fee too.

There are also apps for androids that offer true caller ID, that can display even more

Current Caller ID is a new (free!) caller ID app from WhitePages for your smartphone that augments that boring old White Pages data -- name of caller, city, phone number -- with peripheral information about the person on the other end of the line: Whenever you get a call, you will not only see your caller's name, number and locale; you'll also get the weather where she's calling from, a local news headline from her city, her latest Facebook update, a tweet she just sent out, and her current employment listing on LinkedIn. According to a press release from the company, all of this extra info can "ignite highly engaging phone and text conversations about relevant topics such as social events, travel, accomplishments like promotions and graduations, or a recent concert attended."