Cómo encontrar intervalos de tiempo coincidentes para más de 2 usuarios

Para averiguar cuándo tanto el usuario 1 como el usuario 2 están libres, intente lo siguiente:

select 
a.datetime_start as user1start,a.datetime_end as user1end,
b.datetime_start as user2start,b.datetime_end as user2end ,
case when a.datetime_start > b.datetime_start then a.datetime_start 
   else b.datetime_start end as avail_start,
case when a.datetime_end>b.datetime_end then b.datetime_end 
   else a.datetime_end end as avail_end
from users a inner join users b on
a.datetime_start<=b.datetime_end and a.datetime_end>=b.datetime_start     
and  a.userid={user1} and b.userid={user2}

SQL FDDLE AQUÍ.

EDITADO:Para comparar más de 2 usuarios, intente lo siguiente:

select max(datetime_start) as avail_start,min(datetime_end) as avail_end
from(
        select *,
        @rn := CASE WHEN @prev_start <=datetime_end and @prev_end >=datetime_start THEN @rn ELSE @rn+1 END AS rn,
        @prev_start := datetime_start,
        @prev_end := datetime_end 
        from(
          select * from users2 m
          where exists ( select null 
                          from users2 o 
                           where o.datetime_start <= m.datetime_end and o.datetime_end >= m.datetime_start
                           and o.id <> m.id 
                        ) 
             and m.userid in (2,4,3,5)
           order by m.datetime_start) t,
           (SELECT @prev_start := -1, @rn := 1, @prev_end=-1) AS vars 
) c 
group by rn 
having count(rn)=4 ;

Necesita cambiar m.userid in (2,4,3,5) y having count(rn)=4 según número de usuarios.

SQL FDDLE AQUÍ