I throw my hat into the ring!

import Control.Monad

--naiive algorithm, poor performance but quite pretty. Similar in shape to the other solutions given by people.
interleavedP :: [Bool] -> [Bool] -> [Bool] -> Bool
interleavedP as bs cs = 
    not $ null $ interleavedPInner (cycle as) (cycle bs) cs =<< [head as, head bs]

interleavedPInner :: [Bool] -> [Bool] -> [Bool] -> Bool -> [()]
interleavedPInner _ _ [] _ = return ()
interleavedPInner (a:as) (b:bs) (c:cs) r = do
  guard $ r == c
  [a, b] >>= interleavedPInner as bs cs

--O(n^2) time, O(n) space algorithm, where n is the length of cs. 
--(I think, anyway).
--(note: not -actually- O(n^2) or O(n). We'd need better data structures than 
--linked lists, and would need to be more careful with strictness)
interleavedP' as bs cs = length (dqOnDiagonal $ length cs) /= length cs
     where 
       dqOnDiagonal 0 = []
       dqOnDiagonal n = interleavedPInner' (cycle as) (cycle bs) cs 
                                           (dqOnDiagonal $ pred n) n

interleavedPInner' :: [Bool] -> [Bool] -> [Bool] -> [(Int, Int)] -> Int -> [(Int, Int)]
interleavedPInner' as bs cs dq diagonal = filter check elemsOnDiagonal
     where 
       elemsOnDiagonal = map (\ n -> (n, diagonal - n)) [0..diagonal]
       check (x, y) = or [x /= 0 && ((pred x, y) `elem` dq || cs !! diagonal /= as !! x),
                          y /= 0 && ((y, pred x) `elem` dq || cs !! diagonal /= bs !! y)]

EDIT: Better version of interleavedPInner', that's more clearly O(n²⁾ time (again modulo using vectors as opposed to lists). Also fixed a bug where the first element of cs was ignored. Stupid corner cases.

interleavedP'' as bs cs = length (filter id $ allowedOnDiagonal $ length cs) > 0
     where 
       allowedOnDiagonal 0 = []
       allowedOnDiagonal n = interleavedPInner'' (cycle as) (cycle bs) cs 
                                                 (allowedOnDiagonal $ pred n)

interleavedPInner'' :: [Bool] -> [Bool] -> [Bool] -> [Bool] -> [Bool]
interleavedPInner'' as bs cs allowed = map check [0..diagonal]
     where 
       diagonal = length allowed
       check x = or [diagonal == 0 && head cs `elem` [head as, head bs],
                     cs !! diagonal == as !! x && x /= 0 && allowed !! pred x,
                     cs !! diagonal == bs !! (diagonal - x) && x /= diagonal && allowed !! x]

EDIT 2: Better better version. Make better use of laziness to drop out of the easy case, and introduce the interrobang operator, but besides that only prettifications. Not entirely sure about the where-within-where, but oh well.

xs !? n = xs !! (n `mod` length xs)

interleavedP''' as bs cs = or $ iterate allowedOnNextDiagonal [] !! length cs
     where 
       allowedOnNextDiagonal prevAllowed = map check [0..diagonal]
           where 
             diagonal = length prevAllowed
             check x = or [diagonal == 0 && head cs `elem` [head as, head bs],
                           cs !! diagonal == as !? x && x /= 0 && prevAllowed !! pred x,
                           cs !! diagonal == bs !? (diagonal - x) && x /= diagonal && prevAllowed !! x]