I would try a few things, first make sure that the machine that you are running the build on has ALM registered, also make sure that the ALM url that you have set in Jenkins explicitly has the ALM port number in the URL (usually port 8080) so make sure the URL in jenkins is set to http://OurALMServer:8080/qcbin instead of just http://OurALMServer/qcbin so even if you are using an alias to navigate to the ALM url that does not require you to use the port when accessing ALM, you still need to make sure that the port is part of the URL in Jenkins configuration for ALM.
Additionally whatever URL you have setup in the Jenkins configuration for ALM, this needs to be the same url that you use to register ALM on the machine that will be used to actually run the build you have setup. So if you used http://OurALMServer:8080/qcbin in the jenkins configuration then on the machine that is running the job you need to open IE and navigate to [http://OurALMServer:8080/qcbin/start_a.jsp?common=true][1] this will register ALM on that machine.
[1]: http://OurALMServer:8080/qcbin/start_a.jsp?common=true