I could manage to do this, but I had to use SQL (“delete”). YOU MUST BE VERY CAREFUL WHEN USING THIS COMMAND. DON’T FORGET TO BACKUP YOU WP DATABASE!
There are two tables where WP stores the relationships of categories to posts. These are “wp_term_relationships” and “wp_term_taxonomy”. You can find the ID of the “uncategorized” (probably “1”) in the table “wp_terms”. Then you need only a “delete from ‘wp_term_relationships’ where ‘term_taxonomy_id’=ID_YOU_FOUND” and than “delete from ‘wp_term_taxonomy’ where ‘term_taxonomy_id’=ID_YOU_FOUND”.
This done the job for me.