The mucus lining of the human airway epithelium contains two gel-forming mucins, MUC5B and MUC5AC. During progression of cystic fibrosis (CF), mucus hyper-concentrates as its mucin ratio changes, coinciding with formation of insoluble, dense mucus flakes. We explore rheological heterogeneity of this pathology with reconstituted mucus matching three stages of CF progression and particle-tracking of 200 nm and 1 micron diameter beads. We introduce statistical data analysis methods specific to low signal-to-noise data within flakes. Each bead time series is decomposed into: (i) a fractional Brownian motion (fBm) classifier of the pure time-series signal; (ii) high-frequency static and dynamic noise; and (iii) low-frequency deterministic drift. Subsequent analysis focuses on the denoised fBm classifier ensemble from each mucus sample and bead diameter. Every ensemble fails a homogeneity test, compelling clustering methods to assess levels of heterogeneity. The first binary level detects beads within vs. outside flakes. A second binary level detects within-flake bead signals that can vs. cannot be disentangled from the experimental noise floor. We show all denoised ensembles, within- and outside-flakes, fail a homogeneity test, compelling additional clustering; next, all clusters with sufficient data fail a homogeneity test. These levels of heterogeneity are consistent with outcomes from a stochastic phase-separation process, and dictate applying the generalized Stokes-Einstein relation to each bead per cluster per sample, then frequency-domain averaging to assess rheological heterogeneity. Flakes exhibit a spectrum of gel-like and sol-like domains, outside-flake solutions a spectrum of sol-like domains, painting a rheological signature of the phase-separation process underlying flake-burdened mucus.