" You are not able to challenge xxx "

I'm often getting this when doing "Rematch"

"Find out more" is useless.

The "funny" thing is that sometimes, while I cannot challenge the guy, they challenge me!

What's that message, why can't I challenge the guy?

There can be several reasons. They may have blocked you, as @Taterboy37 mentioned, or maybe they already started a new game (this is the most possible reason), or they simply turned on the setting that they only accept challenges from friends.

Ok ... but it's a rematch, not really a challenge.

And it happens at least 50% of the times, thus I doubt they all blocked me! (moreover, I never played with most of them before)

Well, given how the site behaves since the big upgrade (a few months ago), it's probably one of the many bugs.

In this case the message is different, it's "... is playing"