Oooh, sneaky. I think I figured out the problem. The random order is a big part of the problem, but it would work just fine if you were displaying every product in your catalog at once.

When forms are submitted, the data in them is sent to whatever URL is in the action attribute of the <form> tag. In Drupal, this is nearly always the same page the form is on. So, when the Add to Cart button is clicked, the page is reloaded. On the random order views, you don't necessarily have the same products on the page that you did when you clicked. The Form API's security measures notice that the POST data don't match the form anymore, so nothing happens. Usually, this kind of thing throws an error, but this isn't a usual kind of bug.

If you're going to use the random sorting, I recommend not using any forms in the View. Just use links to the product page.