I was experiencing the same problem in Ubuntu 14.04.
I assume the problem was related to the /lib64/ld-linux-x86-64.so.2 symlink as described above.
As a workardound to avoid booting into live-cd I just replaced the link with ln -sf:
ln -sf /lib/x86_64-linux-gnu/ld-2.17.so /lib64/ld-linux-x86-64.so.2
Valgrind now appears to be working normally.
I was experiencing the same problem in Ubuntu 14.04.
I assume the problem was related to the /lib64/ ld-linux- x86-64. so.2 symlink as described above.
As a workardound to avoid booting into live-cd I just replaced the link with ln -sf:
ln -sf /lib/x86_ 64-linux- gnu/ld- 2.17.so /lib64/ ld-linux- x86-64. so.2
Valgrind now appears to be working normally.