I believe the discover pane is updated from the internet - do the users have access? It almost sounds like it loads a cached view then when it realizes its out of date, flushes it and tries (and fails) to get access. Can the users successfully navigate to tableau.com?
A screenshot may also help illustrate the issue.
Thank you, Nathan.
They are able to access tableau.com through their browsers. Perhaps it's a firewall issue?
That is totally possible. You may want to check out the Tableau Desktop logs to see if there are any error messages. Check out Step 1 in this article for setting up clean logs: http://kb.tableau.com/articles/howto/sending-desktop-logs and then launching Tableau Desktop in Debug mode (then close it after it fully loads so it doesn't keep logging) and then take a look at the logs to see if there are any errors. You can launch Tableau Desktop in debugging mode by navigating to Start > Run and typing in to the Run box (with the quotes): "C:\Program Files\Tableau\Tableau 10.1\bin\tableau.exe" -DLogLevel=debug
Logs are a bit difficult to read, so you may want to open a case with Tech Support: http://www.tableau.com/support/request
Hope this helps!