I found the thread you were talking about, it looks like if I can make it work in the tiny (the thread was about a 168 or 328) I can have pretty much any PWM speed I want! The key is that there is another different register that the TOP count value can be compared to, one that isn't the duty cycle register for the other PWM output.
I'm hoping the tiny85 can do it also, that'd be perfect!
Haven't had a chance to play with it, I did get the prototype fan controller perfboarded though. Might have some time this weekend.
Whenever I do get a chance I will definitely report in with what I find!