And, have you seen the note:

do not complain if you change the array and it does not work ;)

I've checked translator's code. It seems no problem in it.
I've added two fix testcase:

Test.assert_equals(pair_of_shoes([[0,21],[1,23],[0,21],[1,23]]),false)  //@Yuzik's case
Test.assert_equals(pair_of_shoes([[1, 42], [0, 42], [1, 33], [0, 33]]),true) //@seasidetesting's case

After submit, the translator's code returns the correct result.
Perhaps you've modified the input array? @seasidetesting, @Yuzik ;-)

Maybe related to the issue described (I can't see it since I haven't solved the kata, yet — but: I'm working on the Ruby version):

For random tests I get failures, like this one:

Testing for [[1, 42], [0, 42], [1, 33], [0, 33]]
 
✘ It should work for random inputs too -  Expected: false, instead got: true

However, the shoes in that list pair up nicely (the pairs are even sorted in that list!)
Maybe I'm entirely mistaken, but I think this is a bug in the kata's tests.

@GiacomoSorbi,
Ruby issue, please fix it, thanks.