Kan det vara så att du använder FileVault?
När man kör detta frigörs inte diskutrymme förrän du loggar ut eller startar om, kommer upp en ruta om att den vill göra det då också... tar lite tid om det rör sig om flera GB.
Innan jag insåg att det funkade på detta sätt hade jag samma bekymmer och undrade varför det inte blev någon ledig plats trots att jag raderade flera GB...