So the cli() and sei() can be dispensed with, and the minimal code to do the job ends up like this, assuming the interrupt is disabled going in:
EICRA = _BV(ISC11); //external interrupt 1 on falling edge
_delay_loop_1(2); //allow time for the interrupt caused by setting ISCxx (#include <util/delay_basic.h>)
EIFR = _BV(INTF1); //clear the interrupt flag
EIMSK = _BV(INT1); //enable external interrupt 1
Edit 26Jan2013: Playing with this again today, it looks like the call to _delay_loop_1() is not needed. Might have gotten myself wrapped around the axle a bit there last night 
Knowing what I know now, it seems it would have to be one of the latter. Maybe someone can think of a reason that it should work this way, but at the moment, I am at a loss 