After a day's worth of hassle we found the answer. We're still not sure exactly why it happened but the powershell directory disappeared from Hudson's path. Then, although PS3 was installed and the machine had been restarted, Hudson for some reason had not picked up the new PATH variable.
Manually shutting down and restarting Hudson finally got it to pick up the correct PATH and fixed the issue.