Though it is possible that something got deleted, it has been my experience that something gets screwed up in the project file. I have yet to pin down what that "something" is. I've had similar issues when the SDK installation is just fine. There are a couple of options.
First, add all of your files to a new project. This seems to usually work. Kind of a pain, though.
Second, you can right-click project in XCode/Get Info/Build/Library Search Paths. Add new paths similar to /Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator3.1.sdk/usr/lib. Add appropriate versions of that string for each version (2.2.1, etc) and platform (simulator or iPhoneOS). Perform a similar action for Framework Search Paths if frameworks are your problem.
Third, which is more work but more reliable, is to open project.pbxproj from within MyProject.xcodeproj (Textmate is good for this). Look for "/* Begin XCBuildConfiguration section */", then "LIBRARY_SEARCH_PATHS" and "FRAMEWORK_SEARCH_PATHS". Add or modify the paths as appropriate, and save the file.
In any case, a pain in the butt, and I'd sure like to pin-point the cause because I've had this happen a couple of times. Project builds fine, then just up and refuses to do so with what seems to be little reason.