Permalink Issues

I just installed wordpress on my server and I changed the permalink structure from the default ( http://mydomain.com/?p=123 ) to Date and name based ( http://mydomain.com/2008/03/19/sample-post/ ) and now the blog won’t work. Only the homepage is being displayed and none of the permalinks are not working.

Any advice?