With this relatively simple one-off ATMega8535 project I was overconfident and then spent the rest of the day hunting down Timer0 in CTC mode as a 1ms interrupt source not throwing the interrupts.
First of course I did not even realize that it's the Timer0, as much of the program (mostly bit-banging on a couple of port pins) did work, including UART communication (which, being interrupt-driven, indicated that interrupts do work in general). I fiddled around with blinking of the on-board two-colour LED, then looked at the pins with a logic analyzer, and then rewrote the code to use "magic constants" instead of the defines from the avr-libc header (in the unlikely chance that there's some error there) - no change. Then spent some quality time with AS4's simulator (v1, as v2 does not support '8535) just to find bugs in the simulator itself...
Finally turned to google to find a post directly here on avrfreaks, which pointed me to the real problem: the ATMega8535 had the AT90S8535 compatibility fuse on - and truly enough, the AT90S8535's Timer0 does not have CTC mode. To my defense, the ATMega8535's datasheet in the AT90S8535 Compatibility chapter does not care to mention this (thanks, Atmel! :-( ).
The reason for this is, that the target board had been originally designed for the AT90S8535 but manufactured long enough to see the ATMega8535 to be mounted instead. There is an on-board facility to reprogram the '8535 (and it's not a built-in bootloader, as the AT90S' did not permit that, but a second, smaller microcontroller); but the fuses can't be reprogrammed through that. So, instead of attempting to reprogram the fuses through some alternative method, I simply resorted to using Timer2 - which does have CTC mode also in the AT90S' - as the timing interrupt source.
Now the quiz: the board I mention is (was) quite ubiquitous among the AVR users a couple of years ago.. Anyone recognizing it from the above text?