Existing research on cloud network (in)stability has primarily focused on communications between Virtual Machines (VMs) inside a cloud, leaving that of VM communications over higher-latency wide-area networks largely unexplored. Through measurement in real-world cloud platforms, we find that there are prevalent and significant degradation and variation for such VM communications with both TCP and UDP traffic, even over lightly utilized networks. Our in-depth measurement and detailed system analysis reveal that the performance variation and degradation are mainly due to the dual-role of the CPU in both computation and network communication in a VM, and they can be dramatically affected by the CPU's scheduling policy. We provide strong evidence that such issues can be addressed in the hypervisor level and present concrete solutions. Such remedies have been implemented and evaluated in our cloud testbed, showing noticeable improvement for long-haul network communications with VMs.