You may also wish to try one of these.
*nix server:
– from my experience wordpress looks in its root folder for the .htaccess file i.e yoursite.com/blog means you need one in the blog folder.
– create an empty text file and call it exactly “.htaccess” not “.htaccess.txt” or anything.
– give permissions for world read\write\execute (777 i think) – this only temporary
– in WordPress admin set the permalink as you wish and update
– refresh your main page and test a link
– reset the file permission
– refresh and test a link again
Windows:
– try creating a php.ini file at your site root with just these lines in it
cgi.fix_pathinfo = 1
cgi.force_redirect = 0
Hope that helps