I got the issue resolved. VMs are successfully getting launched on the vSphere server now.
It was not even related to jenkins or the vSphere Cloud plugin.
It was the Leap Second bug on the jenkins server that was causing the problem.
I took a jstack of the jenkins process while the slave was stuck at launching and found that the thread was hung at :
"pool-6-thread-8" daemon prio=10 tid=0x00007f75d8252800 nid=0x7292 sleeping[0x00007f768651c000]
java.lang.Thread.State: TIMED_WAITING (sleeping)
at java.lang.Thread.sleep(Native Method)
After spending a lot of time peeking into the source code I realized that even a simple program to sleep for 1 second using Thread.currentThread().sleep(1000) was also getting stuck indefinitely.
Fortunately, I found the reason at http://stackoverflow.com/questions/11294573/thread-sleep-never-returns and a simple reboot of the server solved the problem.