I also ran into this same problem
when porting my own Arduino-derived project (Sanguino-based) from 0022 to 1.0 (same board = works in 0022, "Invalid device signature 0x000000" in 1.0), and the solution above seems to work for me.
@mellis, if you still happen to be watching this thread :-) - do you have any additional information as to why this works, what changed or what the underlying problem was/is? I'm hesitant to start distributing what seems like a "voodoo fix" with the project without any understanding of the underlying problem, or whether these ("stk500"/"arduino") definitions will flip again in 1.0001, etc. (@Coding Badly has a possible explanation in the thread linked above, but it's just a guess so far.)