Page permalinks not working

I have a customer that I’ve installed wordpress with woothemes’ Woocommerce plugin with woostore theme. Now the permalinks for the products (which are posts) works just fine, but I can’t use a custom permalink for Pages. The pages return a 404 when anything other than the default is used. I’ve disabled and uninstalled plugins and nothing has worked…

Where do I go from here?