Changing My Permalinks - Market Press

So for some reason when I change my permalinks to post name or anything but default, all my links/locations convert over to 404 not found.

My webiste is hosted through a yahoo domain.

Is there some reason I can't change the default? Just curious what tips/ideas others have to address this issue.