How does Drupal find contributed modules and themes?
Based on the error message you are getting, "failed to open dir: Permission denied in file_scan_directory()," I would assume that directory access settings are in fact not correct. The user running your webserver can apparently not open sites/all/modules. The best way to check this is to actually switch to the user running the webserver and try to open the directory. A common example would be a user named "apache" for the apache httpd.

On a Linux/OSX system one would often run the following command to accomplish this, though it could vary if your distribution already has a default shell for the user, or supplies a different one from bash. The example is from ubuntu, assuming you are using a normal user account with sudo privileges.

sudo su apache -s /bin/bash


How to do this in Windows I don't know, though I assume it's possible.