(Slight repost) I made a Boxit solver in JavaScript, and couldn't manage to find an unsolvable starting board after going through something like 10000 starting boards. The full space is 25!, which even when accounting for color exchanges (5!), symbol exchanges (5!), row exchanges (5!), column exchanges (5!), and transpositions (2) is still around 1.6e22, so my search has not been exhaustive by any means.
So, I would be pretty interested if there is, in fact, an unsolvable board :).
Edit: I have constructed an unsolvable board by hand ("fodwqbutimrgkexncvpjyshla"). Still, I wonder if there are other unsolvable boards apart from its reflections. Even better if they are unsolvable because it is impossible to get them down to one tile, not because it is impossible to move from the very beginning. (If this is the only group of unsolvable boards, then landing on it (1 in 1.6e22) would be equivalent to getting ~73 coin flips landing heads.)