I also get this problem.
I enlarged the partition and reduced the number of backups from the default 5 down to 3. The message has not reappeared, but not sure why, it may do again in the future.
I also cleared the entire drive, but still got the message saying the drive (partition on which I was backing up)was nearly full, which it obviously wasn't.
Anyone else suffered this?