Can you please try changing the signing tool to SignTool.exe from Microsoft instead? File -> Options -> External Tools -> Use an external tool
If that fails as well you should make sure your certificate provider a member of Windows Root Certificate Program. Also, to avoid such problems you should import your certificate in the Certificate Store of your target machines.