Refus tardif de préavis d'1 mois

Bonjour,

J'ai envoyé (par recommandé avec accusé de réception) une demande de préavis d'1 mois le 26 Septembre 2013 à mon agence, soit jusqu'au 26 Octobre 2013.
En effet, ma compagne a perdu son emploi, pour cause de licenciement économique fin Avril 2013.

L'agence qui s'occupe de notre logement l'a accepté, et nous a proposé d'établir l'état des lieux de sortie le 29 Octobre, car elle ne pouvait pas nous proposer de date plus tôt... Elle nous a donc demandé de régler les 29 jours correspondant au mois d'Octobre 2013.
Nous avons donc réglé le montant correspondant à ces 29 jours en tout début de mois d'Octobre.

Nous devons emménager dans notre nouveau logement le 26 Octobre 2013, soit dans 4 jours.

Nous venons de recevoir aujourd'hui un courrier avec accusé de réception mentionnant que notre demande de préavis d'1 mois n'était pas justifiée, malgré l'accord verbal (et écrit) de notre agence 1 mois plus tôt !
En si peu de temps (4 jours avant), impossible pour nous de changer de situation, il s'avère également impossible pour nous de payer 2 loyers pendant les 2 prochains mois...

Comment faire svp ? Y a-t-il une solution à notre problème ? L'agence est-elle en droit de retourner sa veste moins d'une semaine avant la date prévue ?