UPDATE:

I installed the latest Rubygems from its official website, and wgot rex 1.0.2 (the one compatible with my Ruby version (1.8.7)) from their old gems repo.

It seems, though, that Metasploit is still not able to see where is it installed...