Did you ever want to:
- Have i15d/i18n permalinks?
- Use non-ASCII characters on permalinks?
- Personalize more your current permalinks?
i15d WP is a plugin specifically designed to fulfill this purposes without having to struggle. You just need to activate this plugin and it will be good-to-go. No modification to the core neither template files will be needed.