Is the datasheet of the AVR ATmega32 wrong?
If the system clock is 16 MHz and the prescaler is 256, you timer will run on \$ \large \frac{16\,MHz}{256} = \small 62500\,Hz \$ , so there will be an increment in every \$ \large \frac{1}{62500\,Hz} = \small 16\, \mu s \$. An interrupt will be generated when the counter's value is 31249. If we calculate this time: \$ \small 16\, \mu s \times 31250\, ticks = 0.5\, s\$, which is exactly the same result you have.

The equation in the datasheet is for a different purpose:


  For generating a waveform output in \$ \small CTC\$ mode, the \$ \small OC1A\$ output can be set to toggle its logical level on each compare match by setting the compare output mode bits to toggle mode \$ \small (COM1A1:0 = 1)\$. The \$ \small OC1A\$ value will not be visible on the port pin unless the data direction for the pin is set to output \$ \small (DDR_{OC1A} = 1)\$. The waveform generated will have a maximum frequency of \$ \small fOC1A = fclk_{I/O}/2 \$ when \$ \small OCR1A\$ is set to zero \$(0x0000)\$. The waveform frequency is defined by the following equation: (...)


If you would measure the frequency of specific pin, I think it would be 1 Hz. 



To achieve an 1 s, \$ \small 16\, \mu s \times 62500 = 1\,s\$ interrupt generation you need 62500 ticks and as the counter starts from 0, set OCR1A to \$ \small 31250 \times 2 - 1= 62499\$, and since Timer1 is a 16 bit timer this value is not too high (&lt;65535, \$ 2^{16}-1 \$).