This was a previous issue,
I am currently using "almost-pretty permalinks": /index.php/%category%/%postname%/%post_id%
It works fine and dandy.
I want to switch to completely pretty permalinks by removing the /index.php part
I am having the exact same problem, when I change the permalinks structure on my WordPress settings to a "Pretty" format, all the links to pages are updated but when clicked they give a 404 not found error.
The solution that was suggested has not worked for me. My blog is http://www.sixfiftyseven.co.uk and is hosted at sixfiftyseven.uuuq.com.
Can anybody give me some insight as to why this would not work for me? I have a writeable .htaccess file. I am not an expert and this problem is driving me crazy, I just can't see what I have done wrong.