I have had this happen to me as well. I will have matched everything that they asked for, and yet, I couldn't trade with them. There are a few things that could be wrong.
1. Region. I don't know how you set the region when offering. If you can, that could be the problem.
2. They already traded it. Yes, it is possible that while you were getting the trade set up, someone else was a bit faster with the selection, and the trade is already underway. Sadly, the GTS does not notify you or automatically update the list on your DS.
3. Bad card. There was a problem where people were unable to trade on the first 1000+ game cards that went out. Nintendo had them send their games back in, and fixed the problem. This should not be the case if you recently bought yours, or have got your game 3 months after the game was released.