As mentioned in the previous comment, this is related to the bug
https://bugs.launchpad.net/ubuntu/+source/casper/+bug/1489855
"the sequence of mounting changed from root partition then persistent partition (15.04) to 1st persistent then root partition (16.04) for whatever reason."
There is a work around recently updated in the thread for the bug, which I will elaborate on below as the other thread doesn't seem to have as much visibility (comes up lower in the google search when I was trying to work it out).
Create partitions casper-rw and OS
Use universal USB installer, etc to set up the OS partition with casper-rw file large enough to be able to make changes - needed for later step to workaround bug (I did it with 2gb, but surely it requires less)
Boot up with the new USB. Open /usr/share/initramfs-tools/scripts/casper
with root to edit (sudo). Change the function setup_unionfs() to the following :
https://launchpadlibrarian.net/258626969/casper%20function.txt
sudo update-initramfs -u
(Had to uninstall cryptsetup to do this)
Copy the generated initrd.img file from /boot
to another location.
From another OS, delete the casper-rw file in the USB. Copy the initrd.img back to the live partition and change menu item to use the newly built initrd.img.
The next time you boot up from USB, it should now bootup from the casper-rw partition.
This worked for me for 16.04 after a long frustrating time searching for the solution!
Persistence is saved in a file or partition named casper-rw, a persistent home file or partition named home-rw is also possible. A persistent install will save data, program installs, customized desktops, just about everything except some drivers which are loaded before the persistence file is read during boot, (NVidia graphics).
In a syslinux type install, (SDC, Unetbootin, Universal, Rufus, etc), the system resides in the root of the drive as does the casper-rw file. The filesystem for this partition is FAT32 thus maximum size for the persistence file is 4GB.
Prior to 14.04 syslinux type installs could also use a persistent casper-rw and home-rw partition. Persistent partitions no longer work except with grub2 type installs, (mkusb and the original MultiBootUSB).
Mkusb is easy to use, safe, versatile and will make a persistent partition of whatever size you want, it will then use remaining disk space to make a NTFS partition that is visible to both Linux and Windows.
Limitations, well you don't want to unplug a persistent pendrive while data is being written to persistence, luckily mkusb comes with persistence backup tools.
Best Answer
Make persistent live systems boot in UEFI and BIOS mode
mkusb can create persistent live systems with Ubuntu and Debian (including Ubuntu community flavours and several (but not all) distros based on Ubuntu and Debian.
It is possible to make these persistent live systems boot both in BIOS and UEFI mode, both from 64-bit and 32-bit iso files.
Links
help.ubuntu.com/community/mkusb
help.ubuntu.com/community/mkusb/persistent
Demo example
I made an Ubuntu 16.04.1 LTS persistent live drive in a USB 3 128 GB pendrive. This pendrive has been used a lot, and is getting slow, but it is still working. (I think I will soon 'wipe the whole device' to make it faster again.)
Here is the 'console output',
ubuntu-persistent-live-in-bios-mode.png:
ubuntu-persistent-live-in-uefi-mode.png: