I am also having problems with permalinks in 3.0. I put up a page and it would give me a 404 page not found error when I clicked on the link from the menu bar. The template didn’t function correctly (tab graphic didn’t display on all of the entries), either, so I contacted my hosting company to ask for their help with this.
The tech person found that the wordpress information was missing from the .htaccess file (which was the file included in the install) and he put that in, but the permalinks only worked when I set them to the default setting. Any of the other formats do not work. But that did not solve all of the problems, so he issued a trouble ticket and will get back to me.
I will post what I find out, in case it applies to other people.
