It's easier to read your explain plan output if you format it with [code] tags.
The explain plan output from SQL*Plus can sometimes give you more clues than the TOAD version.
The old version seems to join two tables but the new version does not, so I'm not sure I follow the business rule for duplicates. Also you refer to the new version as "partitioned", but the table appears to be partitioned and both versions seem to use partition elimination. Are you referring to the analytic functions?
This is a bit of a guess but using a standard dedupe approach I get this:
Code:
SELECT * FROM schedule
WHERE rowid IN
( SELECT LEAD(rowid) OVER
( PARTITION BY deal_id, leg_type_cd
ORDER BY schedule_id DESC )
FROM schedule
WHERE business_date = :p_business_date
AND src_sys_feed_row_id = :p_src_sys_feed_id );