Depending on how you have your project set up, Xcode won't necessarily re-link dependent libraries. In order to get it to link every time, you need to add the project as a Target Dependency in the build phases of the target you want the library to be linked too.
Say you have a workspace named Test and two projects name TestApplication and TestLibrary. If you have them included in the workspace as separate projects, you will be able to add TestLibrary.a to TestApplication as a library in the "Link Binary With Libraries" section of the build phases of the TestApplication target, but you WON'T be able to add it in the "Target Dependencies" section.
Now, if you move TestLibrary to be a sub-project of TestAppliction (just drag it into the project within the project navigator), you will be able to add TestLibrary as a both a Library to link with AND as a Target Dependency of TestApplication. Adding it as a Target Dependency ensures that Xcode will build (if necessary) and link the library.
Sorry, but it has been a while since I figured this out set my own projects up this way, so I can't remember exactly what the situation is where the library doesn't get linked. I think it was something along the lines of that since it was a separate project, Xcode wouldn't check to see if it needed building again and just linked against the previous library. I do remember though that my work around until I figured this out was to simply touch a file in the project that needed building. I had a file named touchMe that was included as a compile source if the library project that I would touch before building. You could do the same thing to see if that fixes your problem too, if moving the library project into the dependent project isn't an option for you.
Hope that helps.