Hi Alex
Thanks for the advice, however this isn't my first rodeo :) The SMA was updated on all site servers first, which happened within an hour of the NS being upgraded on Thursday last week (with one exception where it took over 4 hours for the SMA package to replicate to that server). The task and package server agent updates were then enabled afterwards. This was all done before the weekend, so they should be updated by now.
Below is a clipping of the NS on the left, and the site server of our HQ site on the right. As you can see both are the same version, however the logs of the site server on the right continue to show errors relating to "HTTP 400 Bad Request" when communicating with the NS.
The same is true for all the other site servers, they all appear to have the same version installed, yet are showing HTTP 400 Bad Request repeatedly in the logs.
Edit: You'll need to open the above image in a new tab, it's cut the right hand edge of it off in the post above.