I'm assuming, from your use of the word "people" instead of explicitly referring to aliens (not that they can't be people too), plus your explicit mention that some/all current Earth cultures will have vanished by then, that we're talking about future humans.
I think that the others have given some excellent advice, but I just wanted to add that in my opinion, you don't necessarily need to come up with completely new types of names, that aren't tied to any current culture. This is for a few reasons:
· While technology such as the Internet, even today, is greatly accelerating the rate of dispersion of memes and other information across previously largely disconnected cultural groups, it also serves to preserve certain things. Thus, for example, people will be watching "African Queen" on their computers and media screens practically forever, unless civilization in the large undergoes some cataclysmic reboot. Thus not only will people be exposed to American English as spoken in that movie (and all the others from a similar period and the same culture), but the names as well; some future people may name their children "Charlie" because of it, just as people imitatively name children today.
· This technological fixation can be expected to extend even more to systems of symbolic representation, and computers which store and track personal information will of course for all time be far less susceptible to transcription errors than handwriting was in the old days.
Thus especially if the customs for last-name transmission remain the same for a significant portion of society, it's not entirely out of the question that someone would be named "Bill Smith", and (when he chose to vocalize, if ever) pronounce his name roughly as you just heard it in your head, a billion years in the future. Certainly other cultures and traditions would arise over so vast a time, and would probably outnumber the ancient forms by far, but they would also have been influenced by them to some degree. I find it more likely that many languages and pidgins would contain little snippets of at least half-recognizable sounds from today, than that all cultural influence from today would have vanished.
I will update this if I think of a good example, but one approach I've seen in some cases to naming is to take some recognizable forms from today, and apply various degrees of changes to them to indicate the passage of time. Thus instead of "Bill Smith", a writer might name a character "B'yll Smit". That sort of thing always seems labored and cheesy to me if not done with an extremely fine touch.
In any event, I think that your task, which depends on how far into the future your story is cast, is not really to make everything seem completely different from today's world, but rather to determine how much of today's culture remains, morphed though it may be, and what sorts of new changes and additions have occurred. So you'll need some techniques for generating new-type names that are believable in light of your future culture(s), and you'll have to think long and hard with how that meshes with the remnants of today's cultures, in light of the history that will have happened in between. The question is not just what will have happened to isolated splinter cultures, but what happened with the ones that weren't isolated but still evolved.