Well there is good news and bad news.
The good news is, I've reproduced your problem. 
The bad news is, the fix is not totally working. 
I hooked up my 1284P to my Ethernet Shield Rev 3, and found that (using the logic analyzer) although the signals were going out as expected, nothing was coming back.
Then I took a closer look and realized that the shield is designed to interface with the ICSP header (underneath) rather than pins 10/11/12/13 because it is designed to be plugged into other boards, like the Mega.
So I moved SCK, MISO, MOSI to the ICSP header.
Atmega1284P Ethernet Shield
SS pin 5 (D4) D10 on the shield
MOSI pin 6 (D5) ICSP pin 4
MISO pin 7 (D6) ICSP pin 1
SCK pin 8 (D7) ICSP pin 3
Now at least it got a response. But still rather flaky. It didn't hang on the connection any more. Just "failed".
I made the change I mentioned to the w5100.h file. I experimented with slowing down SPI:
// start the Ethernet connection:
Ethernet.begin(mac, ip);
SPI.setClockDivider(SPI_CLOCK_DIV16); // slow down SPI
It connected a couple of times, it got data back a couple of times. You may have more luck with your wiring. I think I have a lot of noise here, I am having trouble uploading the sketch.
This should get you closer.