Sometimes for whatever reason, Time Machine doesn't auto-delete backups to make space for new ones. If you have this problem you might try getting it going again by manually deleting one or two of the oldest ones. Here's how to safely do this, using the Time Machine interface.

Enter Time Machine and select the backup you want to delete.