Suppose you have a seemingly pure function that you want to call a lot of times. Since the results are independent, it makes sense to use threading to speed things up. However, what if the function you call is already threading things behind the scenes? In this case there's multiple levels job dispatch code running and making things unnecessarily slow. Is there a name for this? How do you avoid it, if you aren't familiar with the implementation of the function? Are there other similar pitfalls to multithreading?

I don't know any particular name for that. It's some sub-category of resource starvation bug.

I imagine the same thing only with locking instead of spawning new threads is relatively common.

This is an API design issue. There are two ways to solve it: document the API as spawning threads, or create a blanket policy that a single function call will never thread anything behind the scenes, i.e. you have to explicitly ask for a threaded solution in order to get one.

What makes the most sense is very much situation-dependent.

Functions that create threads should be very rare in a good design, as suggested by the composition problems in the OP.

If I was evaluating a library, which created it's own threads instead of allowing me to run it on my own threads, then that would almost certainly be an instant failure in my eyes -- it would be too much hassle rewriting the library to make it usable.
Likewise, imagine a piece of graphics middleware that created it's own window - you'd never be able to integrate it with your existing code.

Instead, functions/libraries/middleware should take as arguments any resources that they require. For a processing-heavy job that can be paralellised, this 'resource' might be a function-pointer that the function can use to submit 'tasks' to the caller's threading system.
e.g. with the structure below, the user of [font="Courier New"]MyFunction[/font] is in control of how threading is implemented, and can make use of any existing thread resources that they have.[source lang=cpp]typedef void (*Callback)( void* );
typedef void (*SubmitTask)( Callback, void* data );

void MyPrivateThrededFunction( void* _data )
{
MyContext* data = reinterpret_cast<MyContext*>(_data);
//...
}
void MyFunction( int x, int y, int z, SubmitTask fnSubmit )
{
MyContext* data = new MyContext( x, y, z );
fnSubmit( &MyPrivateThrededFunction, data );
fnSubmit( &MyPrivateThrededFunction, data );
fnSubmit( &MyPrivateThrededFunction, data );
}[/source]