Permalink not working after fresh install

I just installed a new copy of wordpress and downloaded anspress using the plugins section. I am puzzled as to how Anspress can be enabled to use SEO friendly urls. I have tried search the net and found nothing. I have a fresh copy of WP and Anspress installed in the root dir of the domain. Anspress works fine if WP’s permalink settings are set to Default (domain.com/?p=123) but fail (404) when I select Post Name permalinks: domain.com/sample-post/. The Questions page doesn’t even load up. 

And yes I went to Anspress -> Options -> and saved options. That didn’t resolve the issue.