See also my other comment on MDM custom apps.
We succeeded in creating our own Sym MDM agent (our own logo! on our apple devices) and distributing it. Bypassing the AppStore.
First, we exactly had the same problem (and error message) but in the end we got it working.
Some background info (short). Apple won't let you create apps just like that. You need an agreement. The cheap agreement (developer) let's you install your apps on max 100 of 'your' devices. You need to install a provisioning profile first OR it's done automatically when using the USB cable. Now you all know why this "provisioning profile" button is present in Altiris Mobile Management solution (the web interface).
Or; you can buy an Enterprise Developer Agreement. Now, you can create apps that anyone can install (following your own procedure which of course is correct).
It looks like you are installing the non-Enterprise 'signed' app on a device that does not have your provisioning profile installed; at least that is where we first got the problems.
What you can do is use the USB approach, install & start the app on your i* device, then on the iDevice look at settings->general->profiles and see that a provisioning profile is installed.
Regards,
Klaas
PS: the other problem might be in Xcode where you can specify the min. reqs. where the app runs on, like ios5+ and so on but I assume that is not the issue at hand