Jobs stuck in queue "Jenkins doesn't have label ..."

After updating to 2.73.3 jobs now gets randomly stuck in queue and Jenkins says that it doesn't have label .. I can see that some slave nodes (containers) coming up online for a split second then disappears, but then the job(s) gets stuck forever in the queue. The problem is that I do not see anything in the Jenkins logs that's out of the ordinary.

Downgrading to 2.73.2 and recreating the config.xml (global config file) seems to fix the issue for us.

P.S.: What's even more weird is that some jobs run while others gets stuck forever (sometimes).