In models with a low quantum gravity scale, one might expect that all opera
tors consistent with gauge symmetries are present in the low-energy effecti
ve theory. If this is the case, some mechanism must be present to adequatel
y suppress operators that violate baryon number. Here we explore the possib
ility that the desired suppression is a consequence of an additional, spont
aneously broken, nonanomalous U(1) symmetry that is orthogonal to hyperchar
ge. We show that successful models can be constructed in which the addition
al particle content necessary to cancel anomalies is minimal and compatible
with the constraints from precision electroweak measurements and gauge uni
fication. If unification is sacrificed, and only the new U(1) and its assoc
iated Higgs fields live in the bulk, it is possible that the gauge field ze
ro mode and first few Kaluza-Klein excitations lie within the kinematic rea
ch of the Fermilab Tevatron. For gauge couplings not much smaller than that
of hypercharge, we show that these highly leptophobic states could evade d
etection at run I, but be discovered at run II. Our scenario presents an al
ternative to the "cartographic" solution to baryon number violation in whic
h leptons and quarks are separated in an extra dimension.