@ironlion37
So one of two things could be happening:
1. The shortcode is configured by default to show images. As such, the plugin will only fetch posts that have images. If you have a small selection of posts with images, this could be the issue. Options if this is the case are to either add images to more posts, or configure the shortcode not to show images.
2. The previous version of the plugin (1.0) had a bug related to the number of posts it would pull from when selecting a random post. The collection of posts from which the random post was selected was only as large as the number of posts set to display on a single page. By default, this is 10… however, if you set this to 1, your random post would never change. In order to prevent this, the code was updated to select from the 100 most recent matches given the shortcode parameters. Updating to version 1.1 of the plugin should fix this issue.