This bug really was a bad one. I've client with over 200 Debian Linux server. Updating all systems wasn't the problem. With the help of Cfengine I was able to push updates but managing all workstation ssh keys (over 1000+ Windows and Linux/BSD workstations) and testing everything took so much time. Debian shouldn't have modified the package in first place. I also had to upgrade over 30 SSL certificates and a whole new CA for OpenVPN. Luckily VeriSign is providing revocation and replacement of SSL certificates (generally it is not provided free of charge) till 30-June-2008.
How do I find out all weak keys?
You can check all your weak keys with following commands:
# wget http://security.debian.org/project/extra/dowkd/dowkd.pl.gz
# wget http://security.debian.org/project/extra/dowkd/dowkd.pl.gz.asc
# gpg --keyserver subkeys.pgp.net --recv-keys 02D524BE
# gpg --verify dowkd.pl.gz.asc
# gunzip dowkd.pl.gz
# perl dowkd.pl host localhost
You should see 0 weak keys. If you run Debian or Ubuntu Linux upgrade your OpenSSL and fix all the affected softwares. There is also wiki page that will address all your concerns. Overall it lasted for few days for large clients. How many hours did you spend updating Debian systems?