If the library has non-reentrant code, then you can't have more than one thread for the stage -- you can't parallelize it. But it generally won't lead to correctness problems.
curl is actually a great example, because it has an event loop for parallelism (rather than threads). So you would run a single thread for curl, because you wouldn't want more than one thread anyway.
Say you are writing a web crawler. From the network/curl stage, you just pass off pointers to blocks of memory to parsing threads. Parsing threads will be CPU bound so you will likely want to run instances of that loop in multiple threads, and you will be able to do it with no problem, since they don't depend on the curl library. They just take in blocks of memory and output some data structure to another queue.
This is also a good way to compose say the curl event loop with event loops from other libraries (GUI libraries, perhaps). Hence the relation to SEDA (http://en.wikipedia.org/wiki/Staged_event-driven_architectur...).