Sorry for the late follow up. Had a few people with this issue, so now I see the pattern and the solution.
NB! only do this if the device has NEVER connected to the cloud before and has the intermittent red blink while fast flashing blue. If the device has previously connected to the cloud successfully then the problem lies elsewhere and these steps are not required.
Using particle, first generate a new key:
particle keys new
Then put the device in DFU mode and flash this new key
dfu-util -d 2b04:d006 -a 1 -s 34 -D device.der
Then reboot the device and it should connect to the cloud.