Reisebüro bucht falsches Hotel

Guten Tag,

wir haben im Reisebüro eine Reise ausgesucht. Wir sollten sofort buchen, da nur noch 4 Plätze im Flugzeug frei seien. Wir buchten sofort. Nach einer Woche kamen die Reiseunterlagen, es war das falsche Hotel gebucht worden. Sehr ähnlicher Name, weswegen uns bei der Unterschrift wohl auch nichts aufgefallen war, aber völlig anderer Ort, für uns nicht akzeptabel.
Der Reiseveranstalter räumte für eine Gebühr die Umbuchung der Reise ein. Die Umbuchung sollten wir aber wieder in dem Reisebüro durchführen. Machten wir auch, das Fax wurde vor unseren Augen abgesandt. Eine Woche später noch immer keine Reiseunterlagen. Wir riefen wieder den Veranstalter an. Der teilte uns mit, dass keine Umbuchung erfolgt sei.
Mittlerweile war die Umbuchungsfrist abgelaufen, die Stornogebühr belief sich auf 604,- Euro.
Das Reisebüro ist eine Art Filiale, jedenfalls war das Umbuchungs-Fax an ein Hauptbüro gegangen. Die hatten die Umbuchung angeblich versucht, aber festgestellt, dass das Hotel mittlerweile ausgebucht war. Diese Mitteilung hat uns aber nie erreicht, obwohl das Reisebüro (Filiale) im Besitz aller möglichen Telefonnummern von uns war. Die Filiale und das Hauptbüro machen unterschiedliche Angaben, wer wann die Filiale angeblich von der vergeblichen Umbuchung benachrichtigt hätte.
Die Stornogebühr haben wir bezahlt, wollen sie aber vom Reisebüro zurückhaben, geht das?