I suspect that your earlier efforts to install put the Perl wrapper files in place - enough to confuse ppm - but not the compiled files. (In my site/lib/auto/Math/Random directory are Random.bs, Random.dll, Random.exp, and Random.lib.)

Try ppm install --force Math::Random - the force option will make ppm replace whatever is currently in place.