why arent my permalinks working?

Hey, how did you fix the prolem with the permalink? I seem to be having a smiliar problem too. Pl help.
Currently i am using the default permalink structure (http://ktens.com/?p=123). However, when i change it to any other structure (say, http://ktens.com/2008/07/07/sample-post/), the links to the post redirect the reader to the homepage of my hosting service provider.
Pl help.