If two machines (virtual or not) must be made to communicate with each other, then establishing a VPN between them cannot harm; by definition, the VPN aims at emulating an isolated set of wires between your two hosts (hence presumably free from hostile eavesdropping and interference) so that arbitrary traffic between the two machine becomes "secure". OpenVPN has good reputation and is free, so using it is not a bad idea. Alternatively, if the applications which must talk to each other can handle their own security (say, SSL), then that is also applicable; the VPN, though, is probably simpler to set up, and more comprehensive.
As others have said, if your machines are VM, then the cloud provider is God: if he wishes so, he can technically see all your secrets and alter them at will. The provider is thus trusted. So the provider cannot be an attacker, and must be assumed not to fall under hostile control. Under these conditions, if the provider can set up a "private link" between your two machines (a VLAN, indeed), then that's fine. The security of the VLAN is strong as long as the actual wires and routers of the provider's network are clean and honest, which is, as I just wrote, a core assumption of the Cloud model.
Now, of course, there can be a subtle difference between "the service provider is honest" and "the service provider is honest and competent". A small configuration mistake (the dreaded human error) can put third party systems onto your VLAN. There again, running your own VPN can add protection against the provider's vagaries (it would not stand against provider's malice, but incompetence is much more common than wickedness).
Edit: I forgot the classic argument about performance. It goes thus:
- Performance issues do not exist.
- Performance issues do not exist until duly measured.
So if you fear performance issues, then the only sane way is to try, and see if the fears were justified or not. One can make a priori estimates but this requires some intimate knowledge of both the behaviour of involved algorithms and of network protocols and latencies; you cannot realistically hope to get decently accurate estimates unless you are highly competent in cryptography, low-level programming and TCP/IP internals. Trying out and quantifying issues is a much better way; more often than not, alleged performance issues happen to be non-existent (but other, unpredicted performance issues may unexpectedly appear). If you want to make benchmarks on OpenVPN, you should first read what has already been done on the subject, namely this page.