Permalink Options Not Working

I wanted to switch to the month/title permalink option, but when I do I get page not found errors.

At first I thought well it is because I had originally posted the articles with the $p=3 format, and now they are renamed so the links are all screwed up. But when I posted something new, it did the same thing.

Has anyone heard about this? I am hosted on GoDaddy servers which are traditionally pretty whack so I don’t know if that is the problem or not. Thanks for any help you can give me.