Instead they said, "Hey, we were giving the average employee $100/mo in parking. We're gonna keep doing that in the form of cash. But, to fund that extra 100 you're now getting in cash, anyone who wants to use the lot has to pay its market value." In short, instead of providing a "flakey parking availability" they provided cash. It's a lot (a lot... get it?) like selling the lot and giving the proceeds to employees.
This isn't always the best idea (sometimes, similar schemes can be socially unjust), but from an efficiency standpoint, it's hard to beat.
I hear what you're saying about pissing people off, but this should do the opposite. Sure, some folks might irrationally like jockeying for position or be early risers. But the company never intended to say "this benefit is for early risers". The intended it as a benefit to all employees and now it is.