On Word Press 3.6.1, there may be a bug in the permalinks screen.
You change the permalinks from default to Date and Name and save the settings. Even after you make changes to the .htaccess file as instructed from the screen, the permalink still does not work.
To fix that, select the Custom Structure, and add in index.php in your URL. See the picture below for the proper format.