Permalinks, index.php/2011/… changing page urls…

I’ve read, and relying on what I read/understood, I took the chance and update my permalink structure from the default p=123 to day/name.

I chose the day/name, then I removed the index.php from the suggested /index.php/%year%/… structure and saved it.

All my page url’s changed from /page_id=whatever to /pageslug.

For example, now I do have a good looking url for the contact page that is mysite.com/contact

except, I get 404.

I cannot get to my pages anymore. All of the good looking URLs end up with a 404. How can I flush/update the permalinks structure?

On this page, ( http://codex.wordpress.org/Using_Permalinks ), there is a section that talks about this;

Permalinks to pages don’t work
If you’ve tried to navigate to a newly created Page and encounter an error, you likely need to update your Permalink structure. Remember, each time you add a new static Page to WordPress, new rules must be generated and updated to .htaccess (WordPress 1.X) or to the internal rewrites array (WordPress 2.X).

The link titled “update your Permalink structure. leads to http://codex.wordpress.org/Permalinks_Options_SubPanel but that does not give much!

Basically, I got stuck with 404.