TIme machine won't back up

[ramw5p]

MBP, mid 2011, doubt that matters. Wont back up to time machine. Says not enough room on disk Disk is 500gb, hdd is 500gb. I had some other stuff, movies, on there, i deleted them but it still won't work, basically time machine hdd [external usb] just won't work. Ideas??? Is there a way to format external and start over??? Im sorta new to OSX [lion] so although i know some, stuff like formatting external hdd etc i am lost on. I did go into time machine and manually delete the files, but it still shows 345 gb used, not enough space to backup???? TIA