I am having the exact same problem, including uninstalling/reinstalling WP on the domain, and the same problem happens. Deleting the theme from within the dashboard doesn’t work, either; the only way to get rid of the problem is to uninstall/reinstall WP. (Good thing I don’t have any content on the site yet!) I tried again with a different theme, and got the same message!
I didn’t change anything about either theme, just clicked “install” and “activate” from within the Manage Themes area of the dashboard.
The only thing I can think of in my case is that I’m using an add-on domain, so maybe WP is looking in the wrong directory for the stylesheet or other aspects of the theme.
This is very frustrating, and would appreciate any tips.
