How to Codesign and Sandbox Helper Application in Xcode 4?
I had exactly the same scenario: a MainApp that contains a HelperApp, which is used to launch the MainApp at login.
The "invalid binary - app sandbox not enabled" problem got resolved by making sure that the Code Signing Identity for both apps in XCode is set to "3rd Party Mac Developer Application".
Then, after submitting for review, I got the "Waiting for Review" notification and no more "invalid binary" errors.
You could try deleting your helper app, then adding it again this way: in Xcode go to file, add new files to "Your project", and import your helper app. Then, make sure they both have valid provisioning profiles for distribution.