I'm not sure I understand the problem. On my machine:
$ ls -l /usr/lib/libprotobuf.so
lrwxrwxrwx 1 root root 20 Jul 3 18:03 /usr/lib/libprotobuf.so -> libprotobuf.so.0.0.0
So, it's a relative link. Yet, everything works fine for me.
It won't work to just submit a patch against the Makefile, because the Makefile is autogenerated from Makefile.am, and I don't think these details appear in Makefile.am.
Maybe it would work better if you installed to /usr instead of /usr/local? Try passing --prefix=/usr to configure. (Be sure to "make clean".)