In Australia they did this a year ago - predictably using common names with a scattering of rare names. Then they did "relationship" ones - sister, boss, mother, etc.
At one stage I saw a coke event of some sort in a mall that looked like you could line up and get a bottle custom printed with any name on it.
It was definitely successful increasing the amount of people talking about coke, even if only to lament that they'd never be able to find their name.