LD cannot find library because of version numbering

It is Debian convention to separate shared libraries into their runtime components (libmagic1: /usr/lib/libmagic.so.1 → libmagic.so.1.0.0) and their development components (libmagic-dev: /usr/lib/libmagic.so → …).
Because the library's soname is libmagic.so.1, that's the string that gets embedded into the executable so that's the file that is loaded when the executable is run.
However, because the library is specified as -lmagic to the linker, it looks for libmagic.so, which is why it is needed for development.
See Diego E. Pettenò: Linkers and names for details on how this all works on Linux.

---

In short, you should apt-get install libmagic-dev.
This will not only give you libmagic.so but also other files necessary for compiling like /usr/include/magic.h.

src: http://stackoverflow.com/questions/335928/ld-cannot-find-an-existing-library