Cloud computing is widely used to provide today's Internet services. Since its service scope is being extended to a wide range of business applications, the security of network communications between clients and clouds are becoming important. Several cloud vendors support virtual private networks (VPNs) for connecting their clouds. Unfortunately, cloud services become unavailable when a VPN failure occurred in a VPN gateway or networks. We propose a transparent VPN failure recovery scheme that can hide VPN failures from users and operating systems (OSs). This scheme transparently recovers from VPN failures by establishing VPN connections in a virtualization layer. When a VPN failure occurs, a client virtual machine monitor (VMM) automatically reconnects to an available VPN gateway which is geographically distributed and connected via leased lines in clouds. IP address changes are hidden from client OSs and servers via a packet relay system implemented by a relay client in the client VMM and a relay server. We implemented a prototype system based on BitVisor, a small client VMM supporting IPsec VPN, and evaluated the prototype system in a wide-area distributed Internet environment in Japan. Experimental results show that our scheme can maintain TCP connections on VPN failures, and performance overhead with the virtualization layer is around 0.6 ms to latency and 8%-30% to throughput.