After struggling with this same problem and following all the accepted answers of updating build settings, clearing the linker search path, etc.. I finally discovered an answer that worked for me.
Before building, make sure you select right type (iPhone Simulator) instead of iOS Device. Then rebuild. Otherwise, you're trying to use a library built for an iOS device (arm processor) on a simulator on your mac (i386). Should've been obvious, but wasn't.
Now, look in the Products group in the Navigator > right click your static library (.a file) > Show in Finder, you'll notice that its in a Debug-iphonesimulator folder instead of Debug-iphoneos. I didn't pay any attention to the folder name originally, or I might have thought of this sooner.
Hope this helps.