Comment 37 for bug 1604750

After a few weeks of use, I have to say the fix -

    [ "/var/lib/apt" -nt "$mycache" ] || [ "/var/lib/apt/lists" -nt "$mycache" ] || [ "/var/log/dpkg.log" -nt "$mycache" ]

to the /usr/lib/byobu/updates_available script has worked well for me on two different systems (both Ubuntu 16.04 with HWE).
After an apt-get upgrade the notification is sometimes still there - but hitting a few F5's (boybu status updates) or waiting until the status update runs again always clears the notification.

Until you solve it you don't need to reboot, you can simply remove the cache file to clear the notification with -

rm $BYOBU_RUN_DIR/cache.tmux/updates-available