If it says access is denied, that means that they have restricted rights on the machine itself for net send. Just like you don't have rights to other people's profiles, you do not have rights to the C:\windows\system32\net.exe file. Can't help you there unless you have administrative rights where you can change the security settings. However, you can pull a net.exe file from another machine and use that one instead. You can put it on a disk and use that file and you will have rights to it.
Either way, if the machines you are trying to send the message to have XP Service Pack 2, the messenger service is disabled, and they will not recieve the message.
Im afraid your pretty much out of luck!