Thanks for responding, Ritesh. I have used the latest multipath-tools, and the problem is not io_setup failed message (which gets rectified via fs.aio-max-nr setting), but the "multipath -ll" freezing for 30 seconds. I have put the snippet for strace during that time. Please let me know if you need further information.
Regards, Ranjan