This error usually happens when there's a very subtle or strange legality problem, and it sometimes indicates a problem in our systems. Could you post the decklist that's doing this?
Longer version: We validate legality in three places (just to be sure), on the client as you build a deck (to be helpful and provide a good UI), on the services as you enter matchmaking (to ensure it's proper for the queue, and because you can't ever trust the client), and then on the actual game rules engine as it gets passed the two decks to use for the game (because the GRE has its own way of looking at the world). This type of error usually means that the client thought the deck was legal, but the matchmaking queue rejected it. That usually comes from other an unusual problem with the deck or a bug with how one of those systems is calculating legality.