Delted "Space" Time Machine Backup
It could be that there are some files left on the time machine drive.  Try emptying the trash.  IF that doesnt work you can run Disk Utility in the Utilities folderin Applications.  Select the disk you want and partition it.  Then you should be able to do a full time machine backup.  Once that operation has completed select that drive as your time machine drive again.