I distinctly remember 2 specific problems: 1) Being unable to get the latest release you wanted to watch. This was a big problem when video stores (not just Blockbuster) would only get in a few copies of new movies. Eventually Blockbuster got some sort of deal with the studios where they would get in something like 100 copies of the latest releases and the problem became #2:

2) Being unable to find anything but the most popular movies. If you wanted to watch that slightly less popular artsy film (but not anything as obscure as a foreign film, just not a (lowercase "b") blockbuster movie), they'd only have a few copies of it, and they'd inevitably all be rented out whenever you wanted to watch it.

I just remember going around the entire store and saying, "seen it, seen it, seen it, don't want to see it, seen it," etc.