What are some practices for getting a name change so that people can find me more easily? For a similar thing, see this thread, where Jay Wacker managed to get people to call him by the name Jay even though he didn't need to get a legal name change. I'm not sure how to go about this though.

The main problem with me is that I have such a frustratingly common name that a lot of people cannot find me when they google me. So many of them simply don't notice the middle initial that I always use in between my first and last names, and this could actually become a major issue in academia, since people have little time and are prone to giving up quickly if they want to look for me (or for my papers) and can't find me at all (I know this having seen how several academics use the Internet and how they look for people's names). This, in turn, could easily ruin my citation count in the future (it's not just that - it's helpful to others when I have a less common name so that they can more easily locate my stuff). I already know at least several people who specifically told me that they tried to find my email but that they couldn't find it (and this isn't limited to just them - there are many, many more - including long-lost friends who have wanted to talk to me for a long time, but who couldn't find me due to said ultra-common name). Of course, people can go through the respective university directories, but how many people really do that? From my observations (when I've seen people look for someone else), very very few do it. Hell, there are even several people at my OWN university who share the same exact first+last name as me.

In Academia, this is even a bigger problem because the vast majority of your connections will be people who only vaguely recognize/know you, so they may know most of the search clues. Even a "full name" + university won't solve all the problems, because I may switch universities and people may only remember the old university that I was in. I'm also very very interdisciplinary, so I want to be searchable to people outside my field as well.

And even if I fix the issue for Google with a massive SEO operation or whatever (that may even be impossible for my ridiculously common name), it's still not going to fix the problem for all of the other ways that people use search.

I'm currently transitioning between undergrad and grad school, so now may be the perfect time for a name change? But I don't know what to do. Is it better for me to change my first name or my last name? The problem is that a citation like "Chen 2011" is going to produce so many entries that no one will ever find them, even though they frequently do google things like that (and I simply cannot prevent people from googling something like that). Chen is so frustratingly common that even a "Chen and Name2 2011" paper could come from some random medical paper rather than from something I wrote.

As an additional complication, the % of Chinese people using the English Internet is exponentially rising, and I can only expect the problem to get worse in the future because of that (and not just for my first name, but even variants of my first name too).
I think people stress too much about the "what if people can't find my papers?" problem. That's what CVs are for. Don't overestimate how often people will actually try to find all of your papers outside of hiring situations. It won't be often. By the time you are established enough to accumulate a significant number of publications, you will be connected to a research university or institute which will make it easy to link you to your publications. 

If "the vast majority of your connections will be people who only vaguely recognize/know you" you've got a problem that changing your name will not solve.

I'd especially like to hear from someone who have had this cause a career problem. My (legal) first name is one of 10 most common, and my last name is in the top 20 (within the US). While this is annoying, it has not caused me any career issues.