Abstract: Using a variant of the Sobolev Embedding Theorem, we prove an uncertainty principle related to Gabor systems that generalizes the Balian-Low Theorem. Namely, if $f\in H^{p/2}(\R)$ and $\hat f\in H^{p'/2}(\R)$ with $1<p<\infty$, $\frac{1}{p}+\frac{1}{p'}=1$, then the Gabor system $\mathcal G(f,1,1)$ is not a frame for $L^2(\R)$. In the $p=1$ case, we obtain a generalization of a result of Benedetto, Czaja, Powell, and Sterbenz.