Published App won't install

Tech-Archive recommends: Fix windows errors by optimizing your registry

I published an application for my users to install. None of them have local admin rights on their machines. When logged in as a regular user and try to install the new program from Add/Remove programs, I get an error that the application requires Internet Explorer 6, and cannot continue. There are Windows XP SP2 Machines, I know for fact that IE 6 is installed.
However, when I log into the same machine as domain admin, the app installs fine, which leads me to think that this is a permissions issue. I was looking through group policy and did see that I can allow elevated permissions when installing applications, but I don't want to do that, as I don't want users installing what ever applications they feel like. Is there something else I can do or check to allow this, I'd rather not have to sit at every workstation to install this app, and I don't want to force install it, as everyone does not need the app.

thanks,

--
NATHAN WELDON