Hmmm.
If dtsrun is not recognized as a command or batch file then I think maybe you have the shortcut setup to execute dtsrun on their local machines instead of on the mapped network drive.
For example, on my workstation the Shortcut Properties shows
Target type: MS-DOS Batch File
Target: V:\rac\run_dts.bat
I have mapped a network drive to the SQL Server machine. On my particular workstation that is drive V: . The drive letter will likely be different on different workstations.
There is a folder on that machine, \rac, and in that folder there is a batch file named run_dts.bat . Inside that batch file are two lines of code, first the dtsrun command with parameters as shown in my previous post, second the pause command.
I used Windows Explorer on my workstation to browse to that file, then right-clicked and Create Shortcut.
As to permissions, I am not sure. It seems likely that a package cannot be run by someone who does not have a login to the instance of SQL Server. Then they would also need permissions to do whatever the package does. I am guessing here. Sorry, I am not a system administrator. ( I simply bribed our sysadmin to give me unrestricted access to our servers. So of course this whole shortcut thing works for me.)
If there are many users who need to run this package, you might consider creating a login which has exactly the necessary permissions and using the /U and /P parameters instead of /E.
Also take a look at Books Online topic dtsrun. Then you will know as much as I do about it.