I was having the exact same issue yesterday. I was using I kind of resolved it, but still don't quite know what's going on. One thing I noticed was that while I was in ArcMap and looking at the excel files in the ArcCatalog window, whenever I was getting the error I was also not able to expand the xls file to show the individual sheets within it. I would get a "dataset doesn't exist or is not supported" type of error. Basically, I'm thinking that it comes down to some sort of permissions issue. I was able to get things to work by alternately closing the python shell/IDLE as well as reopening ArcMap. Also, refreshing the folder in the catalog window helps. Eventually I was able to expand the file in the catalogue window, and also run the scripts.
Not sure if this is helpful, but good luck! It may be worth importing the table to a geodatabase, and using it from there.