Permalink Setting for friendly URLs

Hi, I have installed WordPress fine (well fine for the second time actually) and all appears to be working – well!… until I try and change the permalink settings as follows:
Custom Structure: /%postname%/
(as per step 2 in guidelines at http://tinyurl.com/8jthgv)

I get Page cannot be found. Am i telling it to look for a directory or is wordpress meant to deal with this differently?

All I want is for user-seo-friendly URLs like:

• http://www.example.com/About/
• http://www.example.com/News-Heading/
• http://www.example.com/Another-News-Heading/
• http://www.example.com/Contact/
• etc

That basic structure where everything hangs directly off the domain. I have installed wordpress into the root directory btw. In a previous installation I did try having it in a directory but I don’t think that this is the issue here.

Any help greatly appreciated.

Thanks
Matthew