Classical field theory is insensitive to the split of the field into a background configuration and a dynamical perturbation. In gauge theories, the situation is complicated by the fact that a covariant (w.r.t. the background field) gauge fixing breaks this split independence of the action. Nevertheless, background independence is preserved on the observables, as defined via the BRST formalism, since the violation term is BRST exact. In quantized gauge theories, however, BRST exactness of the violation term is not sufficient to guarantee background independence, due to potential anomalies. We define background independent observables in a geometrical formulation as flat sections of the observable algebra bundle over the manifold of background configurations, with respect to a flat connection which implements background variations. A theory is then called background independent if such a flat (Fedosov) connection exists. We analyze the obstructions to preserve background independence at the quantum level for pure Yang-Mills theory and for perturbative gravity. We find that in the former case all potential obstructions can be removed by finite renormalization. In the latter case, as a consequence of power-counting non-renormalizability, there are infinitely many non-trivial potential obstructions to background independence. We leave open the question whether these obstructions actually occur.