I've tried setting up the search menu, and it works GREAT on simulator (downloaded new file and everything). But on device, says Screen Not Found. The same thing happened with Image Uploader. Is this something I have to resubmit to Apple to make it work? BTW, Thanks David! The search menu works Beautifully! I love that the table menu populates with everything searchable screen, so that its a browser option as well.

Yes, when new versions are released you'll need to re-compile and re-submit. The binary you compiled and submitted to the App Store has zero knowledge of the search feature. Re-compile, test, submit an update, users will be stoked to see your new version too. Generally, it's not a bad thing to continually update your app in the store, users seem to like the idea of somebody 'improving' their apps from time to time.

Now, do I have to include the Search and Image Uploader menus in the app before I submit it? Or will the binary know that they can now be used? The reason I ask is I would like to avoid having two dysfunctional screens sitting on my app for a couple weeks while Apple reviews the update.

You're starting to 'get it' Re-compiling sipmly means that your app will be 'ready' for you to later ad search and image upload and other features that the previous version knew nothing about. This does not mean you have to add them in your control panel. When you do, the app will 'understand' what they are and work ;-)