Se ha preguntado muchas veces, no me he puesto nunca a resolverlo... a ver si lo conseguimos...
 
Vamos por partes 
supongo que tienes un identificador de cabaña (digamos idCabaña) unico sobre todos los complejos....    
Estas no interesan ya que como minimo la primera fecha esta ocupada....    
Estas tampoco por que como minimo la ultima esta ocupada    
Estas tampoco porque tienen algun periodo ocupado entre $fecha1 y $fecha2    
Código MySQL:
Ver original- WHERE-  fecha_inicio <='$fecha1' AND-  fecha_final >='$fecha1'
 
- WHERE-  fecha_inicio <='$fecha2' AND-  fecha_final >='$fecha2'
 
- WHERE-  fecha_inicio >='$fecha1' AND-  fecha_final <='$fecha2'
 
Un UNION DISTINCT de todo lo anterior nos da una lista sin repeticiones de las cabañas que 
no nos interesan... 
Luego     
Código MySQL:
Ver original- WHERE-  fecha_inicio <='$fecha1' AND-  fecha_final >='$fecha1'
 
- WHERE-  fecha_inicio <='$fecha2' AND-  fecha_final >='$fecha2'
 
- WHERE-  fecha_inicio >='$fecha1' AND-  fecha_final <='$fecha2')
 
Nos da el conjunto complementario al anterior... es decir las cabañas libres... 
Creo.... he empezado diciendo que se ha preguntado muchas veces como no lo necesitaba no he leido nunca las respuesta quizas hay alguna mejor... e incluso quizas esta falla.... 
No acabo de ver tu diseño... creo que deberias tener tres tablas  
Cabanias
idCabania
idComplejo
....otros datos de la cabaña  
Complejos
idComplejo
... otros datos del Complejo  
Reservas
idReserva
idCabania
fecha_inicio
fecha_final
.... otros datos de la reserva 
Por no hablar de la tabla Clientes....