Problem solved! As you said, the value max_input_vars had to be raised.
In case anyone has the same problem:
I am on a shared hosting so I don't have direct access to the php.ini file. However, you can create a file names .users.ini (place it in your public_html) and put the following value in:
max_input_vars = 5000
You can choose the value yourself, standard on most servers is 1000 which was too low as I had more than 400 products and apparently you have to do value *4
Alternatively, your host can do it for you if you ask them.
Thanks for the help, great support!