We've found OpenVPN to be our friend here: create an overlay network that doesn't really care if nodes are bare metal or "cloud".
One problem we HAVE seen is a reduction in maximum bandwidth. Since we're CPU limited, however, it hasn't really been an issue.