J'ai réussi !!!
Bon, premièrement, lisez et appliquez le post qu'on ne cesse de répéter :
www.magentocommerce.com/boards/viewthread/2424/
En plus, il a été consulté et validé par un membre de Varien.
Ensuite, le problème que je rencontrais était tout bêtement un problème de date. Avec mon panneau d'administration en français, les dates que je choisissais dans mon calendrier donnaient (et donnent toujours) n'importe quoi une fois sauvegardées.
La solution ? Il y en a 2. Soit mettre l'interface locale de la zone admin en anglais (Etats-Unis), soit dans l'interface française, ne surtout pas utiliser le calendrier et entrer manuellement la date au forme jj/mm/aaaa hh:mm:\ss .
Voilà, ensuite vous sauvegardez, et si la date de début de la file est passée (il fallait le comprendre ça aussi !), vous pouvez sélectionner dans le menu déroulant de la case "Action" l'option "Commencer" ou "Start".
Le simple clic déclenche l'envoi de la newsletter aux abonnés, et le statut passe alors de "Pas envoyé" ou "Not sent" à "Envoyé" ou "Sent".
En espérant aider ceux qui auront autant galéré que moi.
D'ailleurs, il faut corriger le bug de la date française lors de l'utilisation du calendrier.