Newly created Xcode 5 projects have base internationalization turned on. Base internationalization is supported on OS X 10.8 and later. You'll have to turn off base internationalization to support 10.7 and 10.6. See the following Stack Overflow question for more information:
Base.lproj/MainMenu.xib is not available when compiling for targets before Mac OS X 10.8
Another thing you may need to do to support 10.6 is to set the deployment target to 10.6 for both the project and the xib files. I know you said you set the deployment target to 10.6 in your question, but it wasn't clear if you set it for both the project and the xib files. As you're discovering, Apple's project templates do not place a high priority on compatibility with old OS versions.