Well, if your previous employer (and it's company) have a policy about not giving references then I doubt there is much you can do to make them give you one. Usually, companies tend to stick to their policies firmly.
Another thing you could do is to obtain a reference from previous coworkers (in this last or past jobs). Just make sure they are able and willing to do so, and that there is no company policy or rule that would put them in trouble.
Yet, you could also show that company policy to Background Check, so they can see this limitation and back up your claim about not being able (at least not so easily) to provide such reference.
They can then decide what to do in this case, which could be to ask for other sorts of references or them to reach your previous employer by their own means (for which they probably would be denied such reference again).