Drupal 7 Ajax Form, add elements dynamically to a fieldset
The problem was in the AJAX callback, and specifically the code line:

$task_key = (int) substr($name, strpos($name, "_") + 1);


The buttons are named add_todo_key, and the code above returns todo_key, and not the key.

It was solved simply by using strrpos, which find the position of the LAST occurrence of a substring, rather than strpos that finds the first.