Using Explorer View in Sharepoint 2010 - works sometimes

Some users are having issues using the Expolorer View. At first they may get the you don't have permission to do this message, but sometime if they try 3 or 4 times, poof it will then work.

I tried it using a test ID with the same permissions on the site as the user.

Can anyone shed some light on this for me, and help me getting it to work on the first try?

Thanks much in advance.