There are multiple settings that must all be set correctly in order to make this run. (One day, I'd love for Xcode to have a magic "What systems should this program run on?" list that then sets everything up correctly. But that's neither here nor there...)
Project -> Edit Project Settings -> Build Tab: make sure Architectures/Base SDK is set to Mac OS X 10.5.
Project -> Edit Project Settings -> Build Tab: make sure the Architectures/Valid Architectures list includes the system type you're running Leopard on (it's easy to leave out the ppc option).
Project -> Edit Project Settings -> Build Tab: make sure the Architectures/Build Active Architecture Only is unchecked
Project -> Edit Project Settings -> Build Tab: make sure the Deployment/Mac OS X Deployment Target is set to Mac OS X 10.5.
Under Project -> Edit Active Target -> Build Tab: check the same things
Now, you say you had to remove some 10.6 protocol declarations to get it to build. This implies that you'd already done all this (I mostly wrote the top part of the answer for Google's sake; but it's probably still worth double-checking). So now I'm curious what the symptoms for "is not appearing to be executable in Leopard" are.
Does it crash immediately? Does the OS not treat it as an executable bundle? Something else?
Have you tried running the executable from a command line on Leopard (cd into MyApp.app\Contents\MacOS, then run ./MyApp). What happens then? What gets printed to the console when you do it this way?
Basically, you haven't told us what's wrong in enough detail for us to really help out.