Have you tried:
- deactivating all plugins to see if this resolves the problem. If this works, re-activate the plugins one by one until you find the problematic plugin(s).
- switching to the Twenty Eleven theme to rule out any theme-specific problems.
- resetting the plugins folder by FTP or PhpMyAdmin. Sometimes, an apparently inactive plugin can still cause problems.
- resetting your custom permalinks back to the default setting. If this works, then review Using_Permalinks before setting a custom permalink structure back up again.