Ok so I figured this out and am thus answering my own question (if the moderators think deleting this would be more appropriate, please let me know!) . So basically, the second last line in the error log gave away the problem:
error while loading shared libraries: libtinfo.so.5: cannot open shared object file: No such file or directory
Basically Arduino's avrdude was looking for a library file which it could not find. I looked up this particular file and people on other Unix forums said that it has been replaced with the ncurses library file, so I ran the following command to see if I what ncurses library files I had installed currently:
$ find /usr/lib -name "libncurses*"
From this list, libncurses.so.6 seemed to be the most appropriate, which I symlinked to the library file that avrdude was looking for: libtinfo.so.5 in a standard directory /usr/lib where it could be found:
$ ln -s /usr/lib/x86_64-linux-gnu/libncurses.so.6 /usr/lib/libtinfo.so.5
This fixed the issue for me. Here are some links that helped me:
Hope this helps.