The W5100 does not have PWRDN. Do you have PWRDN connected to ground?
What IDE version are you using?
Are you using a W5200 version of the W5100 library?
edit: I submitted one to the Arduino crew here:
http://code.google.com/p/arduino/issues/detail?id=898
Note that you must change a define in that code to use the w5200.