apt-get wants an older GNUTLS version to be defined

Here is how I solved the issue. Note that it seemed a bit dangerous at the end, so a safer approach in another answer or in comments would be appreciated.

I found out there are two versions of libgnutls.so.30 on my system, one in /usr/lib/x86_64-linux-gnu and the other in /usr/local/lib/.

Running nm -gC and readelf -sW with grep on these files shows that the first one does contain the symbol in question and the second does not. This leads me to believe that the wrong copy of gnutls is being loaded at run time.

The file in /usr/lib/x86_64-linux-gnu is a link to libgnutls.so.30.14.10, and the one in /usr/local/lib/x86_64-linux-gnu is a link to libgnutls.so.30.13.1.

Confirmation: Running ldd on libgiognutls shows that it does try to link to the /usr/local/lib version.

More confirmation: Changing LD_LIBRARY_PATH did not work. Looking through the ld.so man page shows that this is probably because some elevated privilege is attained by the time ld.so is called.

Doing sudo su and then changing LD_LIBRARY_PATH. At this point, I am convinced that it is the link priorities of the two versions of libgnutls that is the issue.

Solved: I just took a leap of faith and linked the /usr/local/lib/libgnutls.so to /usr/lib/x86_64-linux-gnu/libgnutls.so file and the same with the .30 versions as well. So far nothing has broken and the error messages are gone.