Data science to the rescue!
The Census Bureau provides shapefiles for Congressional districts every year, so I downloaded (from before the 2010-cycle redistricting) and (after redistricting and most legal challenges to it) and computed the difference between them: areas which changed from one district to another. Here's what that looks like:
It's a fairly large area, but how how many people lived in it? To determine that, I downloaded , which includes the boundaries of 74,002 census tracts with demographic data for each. One of the demographic data points is the number of people age 16+ living in each Tract in 2010, which is a useful proxy for "voting-age population" since these people would be at least 18 years old (and thus eligible to vote) in the next major election in 2012. (The total 16+ population in the United States was 246,211,542 in 2010.)
Now I just had find the intersection of the above area with the census tracts and total the 16+ population counts. Unfortunately that's not simple, since Congressional district boundaries are different than census tract boundaries. A single census tract might be split across two or more Congressional districts. So I tried three different approximation methods.
First, I determined any census tracts that overlap the area where Congressional districts changed. This over-counts, since in many cases only part of the census tract overlaps. The map below shows this constituted 43,604 of the 74,002 Census Tracts, with a total 16+ population of 150,142,547 (61%).
A more conservative estimate would only count census tracts that are entirely contained within the area where Congressional districts changed. This undercounts, since parts of neighboring tracts may also overlap. Nevertheless, this approximation yielded the map below, consisting of 17,229 out of the 74,002 Census Tracts, with a total 16+ population of 57,578,259 (23%).
Note also that this map makes it pretty clear that most of the areas impacted by redistricting were in California, Texas, Florida, and the Northeast.
One last approach is to count the 16+ population proportional to the area of each census tract that overlaps the area of changed Congressional districts. (So if 26% of the area of a given census tract overlaps, count 26% of its 16+ population.) This is still an approximation, since populations in each census tract are not uniformly spread out over the land area, but is perhaps a better estimate than the prior two methods. This approach yields a total 16+ population of 114,361,149 (46%).
So the answer to the original question "what proportion of voting-age Americans saw their Congressional district change following 2010-cycle redistricting?" is between 23% to 61%, with 46% a fairly good estimate, and nearly half of Americans were affected by Congressional redistricting after the 2010 census. That's a lot!
It's worth pointing out that these estimates are for 2010, which may not be indicative of what may happen in 2020. But it's safe to say that between Congressional and state legislative (which I have not considered in this analysis) redistricting, the districts you live in are likely to change in the next few years.