There are no compatible build agents

We have recently upgraded TeamCity from 9.1 to 2018.2 and all builds are working as expected, however we are trying to create a new build and we can't get that to start. The builds sit in the build queue and have an error "There are no compatible agents which can run this build"

The team city console shows that there are compatible agents

I seem to have been able to isolate the problem to a PowerShell runner step, when I create this step the 'Build Step Requirements' field is populated with the PowerShell parameter, in this case "Exists=>(powershell_Desktop_x86|powershell_Desktop_x64)". I know that this is correct because if I create an explicit Requirement with the same settings it still detects the agent as compatible.

I also know that PowerShell is working because if I change the stop to be command line and run "powershell.exe -file path\to\file.ps1" the build starts and runs successfully.

I have looked through the team city server log and can't see any problems, the only entries that are added when running the build are these:

[2019-05-30 14:51:12,695]   INFO - ity.BuildQueuePriorityOrdering - New item Queued build {Build promotion {promotion id=95081, configuration={id=Trunk_WhiteSource, internal id=bt544}}, item id=95081:0:39} with weight 0.00 inserted at the default position 1 in the end of the queue
[2019-05-30 14:51:13,056]   INFO - s.buildServer.ACTIVITIES.AUDIT - build_add_to_queue: Build BUILD_PROMOTION{id=95081} was added to queue by "'tim' {id=79}"
[2019-05-30 14:51:13,352]   INFO - tbrains.buildServer.ACTIVITIES - Build added to queue; Queued build {Build promotion {promotion id=95081, configuration={id=Trunk_WhiteSource, internal id=bt544}, queued build id=95081:0:39, queued}, triggered by "'tim' {id=79}" (##userId='79' type='user'), agent id=39}

The build then just sits in the queue with the three question marks under the time to start and when you hover the speech bubble it says "There are no compatible agents which can run this build" However it does list the agent it can run on.

Any ideas on how to troubleshoot this further?

Thanks

Tim