I spent a solid 3 days on this same issue, but I was finally able to get it working.
I was stuck on the 3rd blinking light, stuck on the connecting to cloud step. After trying a bunch of stuff, I logged into my Verizon FIOS g1100 router. Under the firewall settings, it was set on Maximum security. Reject Filters on Inbound and Outbound traffic. I turned off all filters momentarily just to test and sure enough the Rachio connected. I turned security back to maximum and lost connection. There were ports Rachio needed that were being blocked by my router.
So I went to my access control list and open these ports for outbound.
Port 53 TCP
Port 123 TCP
Port 8883 TCP
That did the trick. Hope that helps anyone having the same issue.