I figured my issue out as being that the intermediate cert did not also contain the root, which is why the deployment service was then failing. Through a bit of trial and error I figured this out, and then once I had combined the two and uploaded it as the intermediate along with the signed then everything kicked in to life.