The classical Balian-Low Theorem is a manifestation of the uncertainty principle, presenting high time-frequency regularity as an obstruction to a function's generating a Gabor frame for L2(IR). The Zak transform allows us to interpret this result as a consequence of the endpoint Sobolev embedding into VMO. Using a variant of this Sobolev embedding theorem, we can prove a version of the Balian-Low Theorem for modified time-frequency regularity conditions; this answers a question raised in a paper of Benedetto, Czaja, Powell, and Sterbenz.