When you do apt upgrade do you happen to have a message in there that tells you something along the lines of “the following packages can be autoremoved and are no longer required”?
What is the output of the following command on your machine:
While cleaning allowed you to work around the issue, there is still a problem with how apt computes free space for the kernel in /boot. For those interested in the details, here is the Debian bug report: https://bugs.debian.org/1085184