Prelink modifies executables and shared libraries on disk so they don't have to be modified every time they're loaded into memory. This should speed up program startup.
Unfortunately, I just tried it in Wheezy on amd64 and it's very broken. An attempt to do a prelink stops with an assertion failure. This could be avoided, if you figure out the what packages need to be excluded. In any case, you're left with an even more serious error: it can't undo many changes because it finds overlapping sections.
I'm disappointed that such a package is available in testing. The same package version can even be found in stable! If someone really wants to play with something this broken, they ought to have to get it from experimental.
Fortunately, this is easy to fix using debsums: simply find modified packages and reinstall them. I used: sudo debsums --changed --no-prelink | xargs dpkg --search | sed "s/:.*//" | sort | uniq | xargs sudo apt-get --reinstall install