Talk to your webhost; your changes are not being written to .htaccess or your webhost doesn't allow .htaccess and mod_rewrite to be used.
See http://codex.wordpress.org/Using_Permalinks
If you're on a Windows server, see http://codex.wordpress.org/Using_Permalinks#Permalinks_without_mod_rewrite