All I did was confirm your code is essentially the same on my SQL2005/1Gig ram 2.8 machine.
My first guess was because you were using a @table variable for your Tally table, I've always heard that @table vars were good only when they had fewer rows.
I ran your code, then substituted my permenant tally table...identical results. second pass saved a few milliseconds due to caching I assume.
/*
Start tally solution
Milliseconds: 3733 | Lines: 25987
Start cursor solution
Milliseconds: 2140 | Lines: 26922
second pass:
Start tally solution
Milliseconds: 3703 | Lines: 25987
Start cursor solution
Milliseconds: 1983 | Lines: 26922
*/
I've just got to assume that although a Tally table is awesome, there will be situations where it does not perform as well as other methods.
Lowell