Libraries were created by someone to fit some purpose they had. It might sound like a problem you want to use the library to solve, but it might not fit your exact usage. When considering a library you do have to evaluate it.
As a developer, one of your responsibilities is to think about how any library may fit into your software, and whether or not you can make your software and libraries work well together. Certainly as you gain more experience that becomes easier, but when you're a blank slate on libraries, there is a higher initial ramp-up time.
That said, I did find your questions interesting so I took my shot at answering them.
Some well-known languages have very poor library support (e.g. C++, Lisp). To some extent this is mitigated by piggybacking on a virtual machine platform (e.g. JVM, CLR). A corollary question, should all future software be written for a virtual machine platform to increase library support? This is problematic for scripts that don't want to incur the cost of launching a virtual machine every time.
Define "Very poor." C++ has boost, qt, Windows MFC and Win32 API, poco, WxWidgets, and those are just the general use frameworks and libraries similar to what you'd get with, say, the Java API. There are C++ libraries for many things, without having to factor in a CLR or JVM. Plus you can take advantage of the many C libraries out there (glib, curl, Apache Portable Runtime) and wrap them in C++ if you want to feel more C++-ey.
Lisp, though. There are many varieties of Lisp. You have modern Lisps like Clojure (on the CLR and JVM) and they can take advantage of their respective platforms. Common Lisp as a standard has many implementations, and I know there are companies out there building software in Common Lisp. I don't know enough about the kind of library support it has though.
Also, whether or not you should use a VM-based language. That's really up to you and what you want to use and what your company/employer/team are fine with. I will use what I think is a suitable tool for the job, as well as what I'm productive in for a given task.
I use Python and Ruby heavily because it's easy for other people to understand and I can quickly do a task in them.
There is a lot of "reinventing the wheel". Have you ever written a linked-list module in C? Yes, of course you have. I don't enjoy writing linked lists in C, but what is the alternative?
I have, but only as an academic exercise. There are several widely used libraries that provide data structures like linked lists for C, namely Apache Portable Runtime and glib.
The general alternative is to not leap before looking - you'll find reinvention in all languages, and much of that may be due to lack of knowledge about existing solutions.
Also, languages and libraries evolve over time. You're not going to find a library that fully suits your needs at some point in time, and in certain fields, algorithmic invention might be very commonplace.
Can a given library (e.g. libfoo-0.1.2) be trusted as as a basis to write your important software? Is the library tested, documented, and does it implement the features you need? How can you tell?
I base it on usage, community, maintenance activity, and if I must, I will check out its bug/task queue and see if it moves along smoothly. If it's commercially supported, I like to see if they actively update it. I also go by recommendations from developers I trust, as well as from communities like StackOverflow, where certain libraries are just mentioned significantly more than others.
There are libraries which I will trust without question, like boost and qt, and I will trust things from Google to perform correctly because I know Google eats their own food and uses their own code internally to process the bajillions of gigabytes of data they get every day.
For other things, I will evaluate it, read the code, and tailor it or scrap it if it's unsuitable.
Learning a library's API can be as time consuming as learning a whole new programming language.
Languages are easy to pick up, especially once you have experience in other languages and a similar paradigm. Ultimately they boil down to you expressing your logic in text, and being sure the compiler/interpreter knows what you mean.
This could be a factor of poor documentation, or you're using a framework that is significantly scoped (like the Java API). But the secret is, you don't necessarily have to learn 100% of a library to be effective using it. I consider myself a proficient Java developer, but I have not touched parts of the Java API because I have never had a need to.
Single purpose libraries are easier to learn in that regard - they have more limited functionality and hopefully documentation is simpler for it.
If a bug is discovered in a library, what is the proper procedure for fixing the bug in your software? How should the bugfix be distributed to all library users?
I have a lot of experience with this (making boost work on Solaris, making boost work on AIX, making tons of other things work on Solaris, like graphics libraries). Fixing it is the easy part.
If this is proprietary code, then my company would do something like patch releases if it was minor issues. Basically a bunch of fixes rolled into one, and then we notified customers via email that we had a new patch release.
For critical or per-customer issues, the fixes were put into a quick patch and we would either distribute just patched files to users, or release a quick patched release.
For open source projects - file a ticket with the project's bug tracker, and if you fixed it, submit your fix recommendation and a patch.
How should libraries be built and distributed? (For example, autotools obviously got it wrong.) Semantic Versioning is good, but how can this be verified and enforced?
autotools is a bear, but modern make systems are nicer, like cmake. There are more like Apache Maven, and you can use these systems to build and package distributables. I also like buildr, which is a Ruby alternative to Maven (compatible with maven).
How should library dependencies be handled? Can we download and install automatically? Will the versions and licenses be compatible?
Using cmake or maven can help you take care of dependencies, and maven can pull in remote dependencies or from a local server. cmake can do the same, but you do have to tell both these build systems what your dependencies are. Versioning and licensing is mostly your job, but if you were on a system like a Linux with a package manager, this could be mitigated.
Is the license for a given library compatible with your software? How can you tell?
You need due diligence here, because licensing is legal, not a software issue. You can see what the licenses are for various things in your system, and there are sites like FSF's License List and Comments which give FSF's interpretation of various licenses' compatibility with the GPL. Also, consult a lawyer.
What should you do if the library is abandoned before starting your software? What about after starting your software?
If it's abandoned before starting your software - evaluate to see if it's still useful to you, and check it's bug list. You could contact the maintainer and offer to take on the project.
If it's abandoned after - again, you can decide if it's worth it to continue, hopefully it's not so deeply embedded into your code that you couldn't switch it out with some effort. Of course, there are softwares where that is a problem and they get pegged to some old version. You can, though, also take the project under your wing and tailor it to your needs. Contact the maintainer.