Permalinks Problem

I have just switched on pretty permalinks, previous posts work ok and I have the new seo friendly names.

Problem is I cannot change setting on plugin configs, etc.

For instance, If I try to remove a side bar widget when I click the submit button if goes to a 404 and no changes to the site happen. If I try to edit the settings in adsense plugin, no changes happen and I get a 404 error.

I tried going back to the old permalink setting and get lots of errors.

Thanks in advance to anyone who can help with this.