The Python tool you are attempting to publish is based on an installed module to the Python site-packages directory. These tools are not copied to the server.
Solution
Ensure the Python tool has been installed and works on the ArcGIS Server machine before publishing your geoprocessing service. If the tool has already been installed on the server, you can safely ignore this warning.