I don't think it would have a significant negative impact on Facebook at all. I see the value of ad networks as primarily resulting from two features: Having a large audience (network), and knowing the audience well (targeted ads).
Facebook will still have a large audience if people keep using it, even if they all delete their information, so a large audience is a given.
Knowing an audience has two large pieces, identity (i.e. you're user X) and derived identity data, i.e. people interested in HN are interested in tech. The biggest use of all this data is associating users together. If all my data across all the internet was deleted immediately, I bet Google et. al would be able to uniquely identify me within a few days, they wouldn't know I'm the same person whose data was just deleted, but they'd know a wealth of targeting information about me again, and within a few years I'd bet they'd know me just as well as they do now.
My web usage is pretty routine, and humans in general are pretty routine, so I would expect it to generally hold that, without explicit effort to the contrary, we'd all be pretty easily re-identified (at least as much as advertisers are concerned) after deleting our information, and sure, I won't be searching for that exact search query because now my git-fu has improved, but I'm still going to be doing things that identify me as someone interested in and/or using git.
Facebook is going to keep all the derived data from people, and that data is going to allow them to very easily re-target anyone once they have a good feel for what their interests are. And I can't imagine a more transparent display of interests than activity on a social network, it's almost explicitly interest-bound.