Permalink issues

I’m trying to change my permalinks…this problem occurs with anything but the default permalink structure.

I have the Arthemia Premium theme. I’ve updated the access of the scrips and cache files to 777. I get a page not found error page on every page buy my homepage. I couldn’t find my .htaccess file so I created one, didn’t help. I copy/pasted the code from the permalinks page in my created .htaccess page, none of that has helped. When the page not found comes up, the permalink is in the correct structure in the address bar. I’m very confused…may it be a problem with my host?