Same problem
I keep getting similar messages. Tried reformatting the external drive and restarting Time Machine. After two days it again told me the drive was full. There are only two windows when I open Time Machine - one says "Today at 8:05 AM", the other says "Today (Now)". Snort.