I have played since start of premium beta and im well over 20ly away from starter system, I'm more like 50-60ly away and still gets it every time I try to dock at an outpost.
If you're in a "medium" sized ship (that is, Cobra -> Python) there is only one pad on each outpost to handle a ship of that size.
As a result, if you don't request docking within 2 or 3 seconds of the outpost instance being created, even solo, you can get request denied, because an NPC has the pad/clearance.
Put another way, I play mostly solo, and while I flew an Asp & Python, saw request denied probably 1 out of every 10 dockings, like clockwork. Typically it was if I didn't make the request immediately upon entering the instance.
The problem is exacerbated by two changes during Gamma. The first is NPC spawn rate, and the second is the NPC's aren't limited regarding the distance they can request clearance (or they spawn at 7500m, I'm not sure which), while as players, we have to get within the 7500m range before we ask, but we're spawned at 10km.
On rotating stations, you can request clearance much farther away than 7500, but that's not relevant.
Anyway, two ways to solve the problem: Ask for clearance quickly, and/or relog if you don't get the medium pad before the NPC does. Other than that, not much you can do until FDEV fixes the problem, long term.