The problem was that I had Link-Time Optimization set to YES for that static library.
I used a DTS ticket to figure this one out, so rather than try to paraphrase the response I got I'm just going to quote it:
"Actually, the issue lies with the Link-Time Optimization build setting being enabled for your library. Setting Strip Linked Product to YES and Link-Time Optimization to NO leads Xcode to first strip your library before the optimization process during linking (you can see it by looking at your build log); linking fails as the required symbols were stripped from the library. You are getting a successful archive [when setting Stripped Link Product to NO] because no symbols are removed before the optimization process during linking. Setting Link-Time Optimization to NO for your library should resolve the issue." -- Linda Ouandji