Ah yes - I see the issue: DMLOptions needs a DML call to execute such as:"Database.Update(l);", but if you're in an update trigger, then you can't update the existing lead.

One option here is override the Save button with a VF page that calls an Apex method upon load.  However, that doesn't help you for other mass updates such as from a List View, Import, or the Data Loader.

To cover all basis, you could have the trigger call an @future method to update the leads a split second after the update finishes:

trigger reassignLeads on Lead (after update){
    List<Id> lIds=new List<id>();
    For (lead l:trigger.new){
        if (l.IsConverted==False){
            lIds.add(l.Id);
        }
    }
    if (AssignLeads.assignAlreadyCalled()==FALSE){
        system.debug('Assign already called? '+AssignLeads.assignAlreadyCalled());
        AssignLeads.Assign(lIds);
    }
}

public global class AssignLeads{

public static Boolean assignAlreadyCalled=FALSE;

public static boolean assignAlreadyCalled(){
return assignAlreadyCalled;
}

@future
public static void assign(List<Id> lIds){
assignAlreadyCalled=TRUE;
List<Lead> leads=[SELECT Id FROM Lead WHERE Id IN: lIds];
For (lead l:leads){
Database.DMLOptions dmo = new Database.DMLOptions();
dmo.assignmentRuleHeader.useDefaultRule= true;
l.setOptions(dmo);

}
update(leads);
}

}

btw-this works in a "clean" org, but in one of my orgs (has my lead scoring app installed) it won't work due to another @future method "interfering" - it fails without an error despite the debug log showing the leads are updated, which is troublesome.