Kündigung der Wohnung

Hallo,
folgender Fall. Ich habe meine Wohnung frisgerecht zum 31.05.2011 gekündigt. Die Kündigung wurde vom Vermieter in Empfang genommen und gegengezeichnet. Die Wohnung wurde bereits von einigen Nachmieter besichtigt und ich habe offen gelassen, evtl., wenn alles gut läuft, bereits Ende April ausziehen könnte, wenn der neue Mietvertrag für die neue Wohnung unter Dach und Fach ist. Ansonsten würde es bei dem Kündigungstermin 31.05.2011 bleiben. Jetzt hat mein jetziger Vermieter mit dem neuen Mieter ein Mietvetrag für den 01.05.2011 abgeschlossen, obwohl von mir keine definitive Zusage für den Auszug zum 30.04.2011 gemacht wurde, weil ich noch keine neue Wohnung gefunden habe. Wie kann ich mich jetzt verhalten, weil der neue Mieter bestimmt zum 01.05.2011 einziehen will und wahrscheinlich zu diesem Termin sein Umzug bzw. mit dem Umzugswagen vor der Tür steht, aber meine Kündigung zum 31.05.2011 lautet?
Gruss
Qualinesti

Da ist sicher das Gespräch mit dem Vermieter sinnvoll ^^