I was getting following error when I tried to change the permalink setting in wordpress admin:
Warning: preg_match() [function.preg-match]: Compilation failed: nothing to repeat at offset 1 in /path/path/path/wp-includes/classes.php on line 95

So to resolve this see clearly the structure of the permalink in the wordpress admin. I may be as follows:
1) ?%postname% … change it to … /%postname% OR
2) ?%category%/%postname% … change it to … /%category%/%postname%
So you just have to remove the question mark and save and nothing else to do