Could you try rebooting the phone and connecting again? On some Android devices, the BLE stack has seemed to get get in a bad state, this can help.
Beyond that, do you have access to any other devices that you could try? Such as another Android or iOS handset?
These types of problems almost always come down to a problem in the gateway, or corrupt keys in the DK. Since you were able to connect to the cloud before, I don't think the keys would be a problem.