Permalinks go to Not Found page

I just installed WordPress on my personal server. I was trying to change the permalink style, but everytime I use something besides default, I visit a post’s permalink, only to have the browser display a not found message. I have mod_rewrite enabled, and I think its working properly, but these permalinks refuse to work. I tried using the permalinks how-to page, but didn’t seem to find anything relating to my problem.