The deleted programs will stick around until the TiVo needs the space for recordings or suggestions. Because you have doubled the storage capacity it is going to take a while to fill the drive.
-first use the empty (unused) space to fill the drive *1
-second use the deleted recording free space *1
-third suggestions *1
-fourth lowest priority requested recording. Never use Keep Until I Delete *2
*1 both requested and suggestions
*2 requested only