The solution also worked for me! I used the .htaccess generator in the Prestashop backend to add
php_value max_input_vars 6000
to my .htaccess file to temporarily override the standard value.
Since the problem really is only with the actual saving
of the feature values, I delete the line from my .htaccess so the server goes back to it's original setting when I'm done adding features.
My hosting provider also was very helpful in this. They did note that Prestashop really shouldn't need for the max_input_vars to be so high, since it's actually a safety measure of sorts, so maybe this is something that can be addressed in Prestashop v1.5, which I'm really looking forward to by the way!
Still, I'm relieved everything works just fine again!