Determine input frequency of square wave w/ ICR in Atmega328p
Here is your code updated to work, with comments starting with "J:" explaining the changes...

  typedef enum {
      CAPTURE_1,
      CAPTURE_2,
      WAIT
  } timer_state_t;

  volatile timer_state_t flag = WAIT;

  // J:This is a 16-bit timer, so these values will always fit into an unsigned int
  volatile unsigned int Capt1, Capt2, CaptOvr;

  // J:Mind as well make this unsigned and give it 2x range since it can never be negative. 
  volatile unsigned long T1Ovs;

  void InitTimer1(void)
  {
     //Set Initial Timer value
     // J:All measurements against TCNT are relative, so no need to reset
     // TCNT1=0;

     // J: Note we need to set up all the timer control bits because we do not know what state they are in
     // J: If, for example, the WGM bits are set to a PWM mode then the TCNT is going to be resetting out from under us rather than monotonically counting up to MAX

     TCCR1A = 0x00;

     //First capture on rising edge
     TCCR1B =(1&lt;&lt;ICES1);
     //Enable input capture and overflow interrupts
     TIMSK1|=(1&lt;&lt;ICIE1)|(1&lt;&lt;TOIE1);
  }

 // J: Note that it would be ok to start the timer when we assign TCCR1B in InitTimer since nothing will happen when the ISR is called until we set flag to CAPTURE1

  void StartTimer1(void)
  {
  //Start timer without prescaler

  // J: Note that we know that the other CS bits are 0 becuase of the Assignment in InitTimer
  TCCR1B |= (1&lt;&lt;CS10);  

  //Enable global interrutps
  // J: Interrupts are turned on by  Arduino platform startup code
  //  sei();
  }

  ISR(TIMER1_CAPT_vect) {

   switch(flag) {
   case CAPTURE_1:
       Capt1 = ICR1;

       // J: Reset the overflow to 0 each time we start a measurement
       T1Ovs=0;
       doubleOverflowError=0;
       flag = CAPTURE_2;
       break;

   case CAPTURE_2:
       Capt2 = ICR1;

       // J: Grab a snap shot of the overflow count since the timer will keep counting (and overflowing);
       CaptOvr = T1Ovs;    
       flag = WAIT;

       //J: Generally bad to print in ISRs
       //Serial.println(flag);

       break;
      }
  }


  ISR(TIMER1_OVF_vect)
  {
    T1Ovs++;

    // J: Just to be correct, check for overflow of the overflow, otherwise if it overflows we would get an incorrect answer.
    if (!T1Ovs) {
      doubleOverflowError=1;
    }
  }

  void setup()
  {

    Serial.begin(9600);

    InitTimer1();
    StartTimer1();
  }

  void loop() {
    // J: No need to bracket this set with cli() becuase the counter will not be counting until wait is updated

    flag = CAPTURE_1;

    while (flag != WAIT);


    // J: Parenthesis and explicit cast for good luck! ( and to ensure correct size and order for operations) 


     if (doubleOverflowError) {
         Serial.println( "Double Overflow Error! Use a bigger prescaller!");
     } else {
         Serial.println( ( (unsigned long) (Capt2) + (CaptOvr * 0x10000UL) )-Capt1 );
     } 
}