All permalinks bring to a 404

Hi guys, been breaking my head over this. Can’t figure it out.

My site is Utah Auto Scene.
I wanted to implement the /%postname%/ permalink structure. I know it’s not recommended by WordPress but it works very well on another blog I am currently running.

Anyway, so I got it to work, worked fine. Then I needed to create a page. The address is http://utahautoscene.com/site-map/.

Except now the problem is that anytime I create a page, it gives me a 404 error. Posts work fine, and even more mind boggling is that when I click on the standard ‘About’ page, it works fine, not matter what permalinks structure I use.

When I change to the default structure of http://utahautoscene.com/?p=123 everything works fine. When I try anything at all different like %postname% or /%year%/%monthnum%/%day%/%postname%/ or /%year%/%monthnum%/%postname%/ or even /archives/%post_id%, it all goes to hell, while the original ‘about’ page works no matter what.

Could you help me out here? I would love to be able to simply use /%postname%/. If this is not possible, and I don’t see why not being that it works fine elsewhere, I could use something else other than the default settings.

I have tried rewriting .htaccess and read so much about this so far that my head is about to explode and yet nothing helps. http://codex.wordpress.org/Using_Permalinks seems to have a lot of info but so far nothing has helped.

Please try to help.