A stochastic version of the Barkai-Leibler model of chemotaxis receptors in Escherichia coli is studied here with the goal of elucidating the effects of intrinsic network noise in their conformational dynamics. The model was originally proposed to explain the robust and near-perfect adaptation of E. coli observed across a wide range of spatially uniform attractant/repellent (ligand) concentrations. In the model, a receptor is either active or inactive and can stochastically switch between the two states. The enzyme CheR methylates inactive receptors while CheB demethylates active receptors and the probability for a receptor to be active depends on its level of methylation and ligand occupation. In a simple version of the model with two methylation sites per receptor (M = 2), we show rigorously, under a quasi-steady state approximation, that the mean active fraction of receptors is an ultrasensitive function of [CheR]/[CheB] in the limit of saturating receptor concentration. Hence the model shows zeroorder ultrasensitivity (ZOU), similar to the classical two-state model of covalent modification studied by Goldbeter and Koshland (GK). We also find that in the limits of extremely small and extremely large ligand concentrations, the system reduces to two different two-state GK modules. A quantitative measure of the spontaneous fluctuations in activity is provided by the variance s2 a in the active fraction, which is estimated mathematically under linear noise approximation (LNA). It is found that s2 a peaks near the ZOU transition. The variance is a nonmonotonic, but weak function of ligand concentration and a decreasing function of receptor concentration. Gillespie simulations are also performed in models with M = 2, 3 and 4. For M = 2, simulations show excellent agreement with analytical results obtained under LNA. Numerical results for M = 3 and M = 4 are qualitatively similar to our mathematical results in M = 2; while all the models show ZOU in mean activity, the variance is found to be smaller for larger M. The magnitude of receptor noise deduced from available experimental data is consistent with our predictions. A simple analysis of the downstream signaling pathway shows that this noise is large enough to affect the motility of the organism, and may have a beneficial effect on it. The response of mean receptor activity to small time-dependent changes in the external ligand concentration is computed within linear response theory, and found to have a bilobe form, in agreement with earlier experimental observations. © 2017 Roy, Gopalakrishnan. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.