[...]
In this situation, if interleaveStreams evaluates its second argument before returning any work, it will never be able to return.  Happily, the outer Cons of the result does not depend on the second argument.  I can fix the issue just by making the second argument be pattern-matched lazily (with ~, i.e. only as soon as any uses of the argument in the function are evaluated):

interleaveStreams (Cons a as) ~(Cons b bs) = Cons a (Cons b (interleaveStreams as bs))

I'm not sure whether there's a practical difference between these and Data.Stream's definition.  Actually, I think they turn out to do exactly the same thing...