For those impatient the winning sequence of commands (for Debian/Ubuntu) is:
sudo apt-get install libgmp3-dev
cpanp -i Math::BigInt::GMP
and now you can:
cpanp -i --force Catalyst::Authentication::Credential::OpenID
Now the story - at my pristine installation of Perl 5.10.1 on my Ubuntu box I discovered two problems with C:A:C:O installation. First was a trivial POD error, detected with the new pod tests - this is why you need to do that
--force(it is fixed in the dev version). The second is more interesting - installing one of the prerequisites - Crypt::DH seemed to take forever. Fortunately by chance I found a good explanation of the problem in Crypt::DH::GMP docs - apparently for any reasonable performance Crypt::DH needs Math::BigInt::GMP which is not in the prerequisites. Without it it still works - but it can take serveral hours to pass the tests (reported first 3 years ago). So next thing is install Math::BigInt::GMP - unfortunately this is not automatic either - you need to install gmp.h header file first (on Debian/Ubuntu it is the libgmp3-dev package). This is why you need to execute the first two commands.
I hope that will help someone.