I've had that problem when a plug-in is using a shared .dll and Maya can't find the dll. The user had put the shared dll into a directory that was not in the PATH list. Maya couldn't find it and complained with the same message you are getting.
Check the environment setup on the machines that can't load the plug-in.
g-