You might also be interested in this: arxiv.org/abs/math/0501525 Justin Moore shows that, under the proper forcing axiom, every uncountable linear order contains a subset isomorphic to one of 5 different types.

I like Joel's answer better than mine, but I would like to point out that one can sensibly interchange "$L$-valued relation" and "relation in the category of $L$-valued sets". If it's clear that I'm talking about the category of $L$-valued sets, I'm going to say "let $R\rightarrow A\times B$ be a relation", not "let $R$ be an $L$-valued relation".

Thanks! I suspected it wasn't true in general. Fortunately I only need the result in the Boolean case. Neat solution!