Can't "Save Until I Delete"

Suddenly my Tivo suggests I am running out of room - and that I can not "Save Until I Delete" anymore.
Looking at mt disk usage I see that I have 51.9% free space (great) but I suspect it may have something to do with the 46.9% Deleted (why?).

My DailyMail agrees - suggesting I have used around 48.1%.

Any idea how to overcome this ?

Memory Statistics:
total: used: free: shared: buffers: cached:
Mem: 14270464 14139392 131072 54071296 69632 4153344


Space Used - 141819 MB

Expired Suggestion 3 6416 MB 4.5% 2:55:06
Single 13 39712 MB 28.0% 15:20:14
Season Pass 10 17172 MB 12.1% 8:40:14
Wishlist 2 4768 MB 3.4% 2:15:02
Live Cache 1 204 MB 0.1% 0:04:47

Total 29 68272 MB 48.1% 29:15:23

Free Space - Best - 73547 MB 51.9% 28:24:23
Deleted 45 66468 MB 46.9% 32:31:27