https://bugs.freedesktop.org/show_bug.cgi?id=98988
--- Comment #7 from Alex Deucher alexdeucher@gmail.com --- (In reply to John Brooks from comment #5)
The firmware from comment #3 was distributed in linux-firmware starting with commit 5e6165a8705613646c9a5a282f0a7243fe5dafdc (https://git.kernel.org/cgit/linux/kernel/git/firmware/linux-firmware.git/ commit/?id=5e6165a8705613646c9a5a282f0a7243fe5dafdc). Which corresponds to Ubuntu's linux-firmware package version 1.158, released on May 6, 2016.
People who already had this firmware would not experience the regression, which could explain the mixed reports of reproducibility.
The latest firmware from upstream linux-firmware.git matches what Leo posted. I think you just need to update your firmware from linux-firmware.git and Ubuntu needs to update as well if they haven't already.