I hope this will help someone else, what I ended up doing was revoking an affected user's Business Premium licence and waiting about half an hour before assigning the same licence again, then testing the user's access. I was sceptical about this as I'd already done the same thing last week, though at that point I only revoked the licence for a couple of minutes before reassigning it as they didn't want to lose access to Office and OneDrive for any length of time.
After waiting 30 minutes and reassigning the licence, the user was able to use Copilot chat again. I have tested this with one other user so far and had the same result, so it looks like patience and time may be required to apply this fix.