Once your new leads have been created you can click on the + 0 Tasks link, which sits just beneath each of your new leads, and the quick task creation is then just above your leads pipeline for you to fill in.
This will ensure that these tasks are linked with your leads.