There will be a bigger pool of signatures from re-used addresses available, all in one nicely packaged list. The chances of getting a lucky sig collision increase if you're working with a bigger set of targets.

What's with the "if"? Are these actually the valid probabilities for sig pre-imaging of the length of the keys we're using in Bitcoin or not?

Surely it only becomes easier by a miniscule amount. Besides if this were true, wouldn't satoshidice 50% been cleaned out a long time ago?

It's like saying that password made from 35 random symbols are insecure because it is easier to brute force than password made from 37 random symbols. In reality I don't think i ever will become a practical security threat.

Haha.  The University of Hawaii (c/o Wiki Answers) estimates that you'd have 7500000000000000000 (75 x 10^17) grains if you collected all the sand from all the beaches and deserts and ocean floors in the entire world. 

Imagine checking all the sand piece-by-piece to find a private key that gives you the bitcoin address you are looking for (1 : 2^160 odds).  Is it this hard to do?  NO, it is WAY harder than just checking every piece of sand!  Imagine if every piece of sand you've collected could be broken down into the same huge number of pieces (7500000000000000000 pieces), and now you have to check every single one of those 7500000000000000000 pieces that make up each of the 7500000000000000000 grains of sand in all the world.  Is is this hard to do?  NO, its even harder:

(75 10^17) x (75 10^17) ~= 2^125  << 2^160 !!

Not going to happen.

In theory it should be just as hard as calculating the private key. Or the digital signature algorithm is seriously flawed...

In general DSA is pretty lame— there are attacks on DSA with reduced computation compared to solving the DLP given multiple signatures with nonces that happen to have certain properties relative to each other. The cases where the attacks are made possible are themselves unlikely enough that its not a practical concern, but its not correct to say that ECDSA is as strong as ECDLP as far as we know. Instead we know its not, but not concerningly so.

(Schnorr signatures are better in almost any way you can pick— better security proofs, ability to do efficient multisignature, etc. but their creator patented them and so pretty much no one has used them except academics.)

I don't consider increased cryptographic risk from pubkey reuse or disclosure of the pubkey (keep in mind: until you spend using a key the first time the public doesn't even know the EC pubkey you're using, they know its hash!) against real, hypothetical, or quantum attacks to be a major consideration. ... but I suppose you could say that it's just one more reason to not reuse addresses.