Switching Time Machine to a new iMac
Try formatting your Time Machine drive/partition and then add it back to TM. Time Machine's backups are device-specific so you can't overwrite/continue using a backup on another machine. 

You could also try deleting your current backups manually, and then clean the .Trashes folder, however formatting is faster. If emptying the trash doesn't help, try cd /Volumes/drivename and then sudo rm -rf .Trashes