We have specified a mandatory field for the tasks (the "Related To" field). This field is disabled for the Leads' tasks, and therefore, the system does not allow us to create a new task for the Leads.
If this field is not used for the Leads, it should be possible a new task.
In the following image, you can see the alert message displayed by the system: