Have you looked at dba_extents to check what objects are represented by extents that encroach into the area you're trying to remove?

It could be that the first extent of opne of those partitions is "higher" than you think, in which case you could execute a move to get it closer to the start of the data file.