I get messages that my Time Machine backup volume is full and TM has deleted older backups. But my backup target disk is an external 3 TB HD and Finder reports that over 2 TB of it are free (only some 820 MB used)!
I am backing up the internal 1 TB SSD (850 GB in use) of my Mac Book Pro Retina to that volume. I have also reformatted the backup volume and started all over with a new Time Machine backup to that fresh and empty target. But the effect reappears after 3 to 4 days.
All my trials to find similar reports on Google failed. It seems that other users have less than 25% free on their backup target when they run into this message. The only similar question I could find was this one but it was not answered.
I am currently running OS X Yosemite 10.10.1 and the backup HD is connected through USB 3.