If there is no NAT and no FW in between then your edge should be able to reach VCG.
If its still not happening, can you check the CLI command output "debug.py --path", it will show if VCE is trying to build any tunnels to VCG.
Also you can do packet capture on VCO for your internet interface and verify if any udp 2426 packets are going out.
I used VMware virtual gateway to set up a test environment. I also encountered the same problem. I used Wireshark to capture packet analysis. I saw that VCE uses udp/2426, tcp/443 to connect to VCG, and I also saw that VCG uses udp/2426 connect to VCE, but the result of "debug.py --path" shows that RxState and TxState are both INITIAL instead of STABLE. What is the problem ?!
So just to update this thread. Turns out we also had a compatibility problem with our CPUs. They didn't support AES-NI, so that's why the tunnel never came up.
Hope that helps anyone!