permalink & 404

Quite an easy problem to solve but still no solution found…
I read some blogs and finally this forum but I just cannot change the “Ugly”-permalink to something trivial like this:

/%year%/%monthnum%/%postname%/

Also, I have checked my rewrite rules on the webserver, in the WordPress root folder and tried some plugins.

Anything other than that? I would be grateful for some help =)