It might become more difficult, but mostly because most of us don't
care enough about being hard to track down.
Piecing together most of my "online identity" for example is easy, because I don't care. My id here is my first name and last initial. My name is all over my blog which I've acknowledged ownership of in many contexts, even where I use user names that does not match my name in any way, for example. But there are the odd pieces you likely won't find, because I don't want you to find them.
People just need to, and will, learn to curate their identity more.
Incidentally, things like Google's attempt at a real name policy for G+ in some ways makes anonymity easier: It makes people trust names that have not been verified - just eyeballed for "looks like a real human name". Everyone knows that "chimeracoder" is not likely to be your real name. But if you posted as pjohnson (just to pick something at random), people would be likely to assume it is your actual name and be none the wiser.