Start Time Machine all over again?

[dawgfan]

My 160Gb external HD used for Time Machine is getting full. I tried a backup yesterday and the size required was 24Gb with only 21Gb available.

I'm confused because the language in the preferences indicates that older backups will be replaced when room is required. How come this is not happening or what did I not setup correctly?

Thanks!

PS - Failing a fix for the above, how do I completely reformat the ext HD and start fresh with a new Time Machine backup sequence?

Thanks again!