I just found the problem: I had no default menu item. I had actually 4 default menu items for each language (I have 4 different menus for each language). I added a menu with only one menu item, made it default without specifying a language, and now the breadcrumbs work.
Strange, I thought a language-based default item should be enough?
