Ok, just set up a new site with 2.5.1 and page slugs aren't working.
Step 1: I went to the permalinks options and changed it from default to "day and name"
Step 2: I created a page called "test". At the top of the writing window it properly displayed "Permalink: http://www.mysite.com/test/". Once published, it added a "test" link to the pages section in the sidebar.
But when I try to go to the link http://www.mysite.com/test/, I get a 404 error.
Ideas?