I've been reading Parallel and Concurrent Programming in Haskell, and decided my last naive solution could be trivially palatalized using the parsearch function from the book:

import Control.Monad.Par import Control.DeepSeq

parsearch :: NFData solution
      => Int                             -- depth
      -> ( partial -> Maybe solution )   -- finished?
      -> ( partial -> [ partial ] )      -- refine a solution
      -> partial                         -- initial solution
      -> [solution]

parsearch maxdepth finished refine emptysoln
  = runPar $ generate 0 emptysoln
  where
    generate d partial | d >= maxdepth
       = return (search finished refine partial)
    generate d partial
       | Just soln <- finished partial = return [soln]
       | otherwise  = do
           solnss <- parMapM (generate (d+1)) (refine partial)
           return (concat solnss)


parMapM' :: NFData b => (a -> Par b) -> [a] -> Par [b]
parMapM' f as = do
  ibs <- mapM (spawn . f) as
  mapM get ibs

search :: ( partial -> Maybe solution )
       -> ( partial -> [ partial ] )
       -> partial
       -> [solution]

search finished refine emptysoln = generate emptysoln
  where
    generate partial
       | Just soln <- finished partial = [soln]
       | otherwise  = concat (map generate (refine partial))

The challenge then becomes:

challenge :: Int -> Int -> [Int]
challenge size target = 
    let maxdepth = floor . logBase 2 . fromIntegral $ size
        finished (count, total, chain) | count == size && total == target
                                           = Just chain
                                       | otherwise
                                           = Nothing
        refine (count, total, chain) = [ (count+1, total+a+b, a+b:chain)
                                       | a <- chain
                                       , b <- chain ]
        emptysoln = (0, 1, [1]) :: (Int, Int, [Int])
     in head $ parsearch maxdepth finished refine emptysoln