Permalinks Once Again…

I know there are probably hundreds of permalink problems solved out there and that I should read it first, but I looked at a few and none of them helped me. I even read the WordPress permalink page http://codex.wordpress.org/Using_Permalinks but that didn’t help either. I trying to change my permalink to: /index.php/%category%/%postname%/ but it’s now working. I tried /%category%/%postname%/ but that didn’t work either. I didn’t have a .htaccess file so I created one. In it here’s what I put myself:

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>

# END WordPress

But still for some reason it doesn’t work. It used to work on my old domain, but I swtiched to godaddy.com and it doesn’t work anymore.