I was wondering, if you want to make a NBA game on smartphones, without the license held by EA, the first solution seems to name your teams with a different name, such as "Chicragro Brulls" (this is just for the example), but would it be possible to just call your team with the name of the city, such as "Chicago vs. Dallas" ? I know the first solution was chosen by Pro Evolution Soccer, would you know any other game that don't use a license?
I am not a lawyer. This is not legal advice. Blah, blah blah...
Obviously this all depends on where you are doing business, but regardless, I'm going to play devil's advocate here and say that while city names are not protected trademarks, you can still be taken to court based on likeness of the name. Especially if you use the same team colors, and so on.
If you want to be on the safe side, just come up with a few dozen new team names and let players rename them. If the player wants to make the Chicago Bulls, then they can name the team that and setup the jersey colors to match.
Better yet, don't even try and compete with EA Sports (and the other AAA sports-realism game studios) and build a basketball game that is more unique: like a bunch of gangs playing street-ball where there are no real rules except put the ball in the hoop. That sounds like way more fun anyway. ;-)
I'm not a lawyer, so this is just my interpretation of the law. Before you release anything, talk to a lawyer. Your legal decisions are your own.
Names of cities are not protected trade marks (yet?), you can use them how you like. You may also look into giving the city name as the default and allowing the player to change the name of the team if they desire.
As far as other games that may employ similar methods, I don't know, and it's not really on topic for the site.