You need to create a blank htaccess file – use any text editor Notepad or Text Editor and create a file and save it as .htaccess (save it as DOTHTACCESS) – load this up to the root of your ftp space (that is in the same folder with wp-config.php) then right click on this and change the permissions to 777 , then login to wordpress and go to permalinks, choose post name, and click save.
This will then cause the core pages & posts & categories on your site to have a nice written url.
But!!! – You will then need to manually change all your old page links
for example if you have linked to say contact us on some homepage text
to the new permalink ones…
Main menu and widgets ones will automatically update – but manually added links in pages need re- done by hand.
———————————————
Below is info for me for future reference
A) Have you verified that you actually modified the correct .htaccess file? It should be the .htaccess file that is in the same folder with wp-config.php
B) Have you gone back into your admin area and tried to re-save the permalinks? When you save the permalink settings, it flushes out any old information about permalinks and recreates it, so that might help.
C) Have you verified that mod_rewrite is installed and activated on your Web server? If you don’t know, that may be something to ask your hosting company.
D) Have you made sure that .htaccess files have the proper allowances to override server-wide settings? Again, that’s something you’d have to ask your Web hosting company.