Hi,
Say I use a 32.768Khz oscillator as a timebase and feed it into an 8 bit counter with a 256 prescaler. That means it should interrupt 128 times a second or once every 7.8125 mS
No, in that case it will interrupt every 2 seconds. The counter "ticks" at 32768Hz, it counts from 0 to 65535 (256*256) so it takes 2 seconds for it to overflow and trip an interrupt.

So once an interrupt occurs the counter stops and my code begins to run. When the code is finished the interrupt is cleared and jumps back to counting.
Yes, when it interrupts the processor stops doing what it was doing and starts servicing your interrupt but the counter does not stop counting. It keeps counting in the background at all times - unless you tell it to stop.

32.768Khz means that one pulse occurs roughly every 30 uS. Does that mean the interrupt and completion of the code has to happen faster than 30 uS or counts would be lost?
Yes, the period of the clock signal for the counter is ~30us but it does not mean that an interrupt is tripped every 30us. The interrupt is tripped when the counter overflows from 255 (in the case of an 8 bit counter) to 0. With a prescaler of 256 it means it takes 256 pulses for every count so there will be 65536 "pulses" between each interrupt. And again, the "pulses" are counted by the hardware so it will keep counting no matter what your code is doing - basically. However, if your interrupt service routine takes longer than the time between two interrupts you'll miss the second interrupt.

I'm a bit stumped on a way around this. Is there a way to keep track of the overflows instead?
Basically that IS what you're doing, the interrupt occurs when the counter overflows.

Keep the counter running like a frequency divider and do something every 128 overflows? 7.8125 mS should be enough time to do a little math and shiftout 32 bits.
If you don't want the counter to count from 0 you need preload it with a "starting value" each time it interrupts. Actually you ADD your preload value to the counter value in order to account for interrupt latency etc - it depends a bit on what you're doing.

/Henrik.