Comment 21 for bug 1247026

It turns out that this problem was caused by libc6-amd64 being installed (this package was pulled in as a dependency of another package). On a amd64 system this does not make sense as the libc6-amd64 package is not "there", its contents is provided by the libc6 package.
Installing libc6-amd64 replaces the symlink from ld-linux-x86-64.so.2 to /lib/x86_64-linux-gnu/ld-2.17.so normally found in /lib64 with a real file version of ld-2.17.so - and makes valgrind not work.

Removing libc6-amd64 and restoring the correct symlink fixes valgrind.
The recipe for doing this is:
1) Close everything (you'll be rebooting in a few sec.)
2) Half-remove libc6-amd64: apt-get remove libc6-amd64 (this causes ld-2.17.so to disappear, so you can't run any commands after this).
3) Reboot the system using a live-cd.
4) Recreate the correct symlink: ln -s /lib/x86_64-linux-gnu/ld-2.17.so /lib64/ld-linux-x86-64.so.2
6) Reboot the system (normal boot)
7) You can now completely remove the libc6-amd64 package.

The real bug in this is that it is possible to install libc6-amd64 on a amd64 system in the first place. This should definitely be blocked.