What are the downsides using random values in Unit Testing?

They are random.

(Your test might randomly work, even if your code is broken.)

Downsides

Firstly, it makes the test more convoluted and slightly harder to debug, as you cannot directly see all the values being fed in (though there's always the option of generating test cases as either code or data, too). If you're doing some semi-complicated logic to generate your random test data, then there's also the chance that this code has a bug in it. Bugs in test code can be a pain, especially if developers immediate assume the bug is the production code.

Secondly, it is often impossible to be specific about the expected answer. If you know the answer based on the input, then there's a decent chance you're just aping the logic under test (think about it -- if the input is random, how do you know the expected output?) As a result, you may have to trade very specific asserts (the value should be x) for more general sanity-check asserts (the value should be between y and z).

Thirdly, unless there's a wide range of inputs and outputs, you can often cover the same range using well chosen values in a standard unit tests with less complexity. E.g. pick the numbers -max, (-max + 1), -2, -1, 0, 1, 2, max-1, max. (or whatever is interesting for the algorithm).

Upsides

When done well with the correct target, these tests can provide a very valuable complementary testing pass. I've seen quite a few bits of code that, when hammered by randomly generated test inputs, buckled due to unforeseen edge cases. I sometimes add an extra integration testing pass that generates a shedload of test cases.

Additional tricks

If one of your random tests fails, isolate the 'interesting' value and promote it into a standalone unit test to ensure that you can fix the bug and it will never regress prior to checkin.