Ethernet Shield (5100) problem, random garbage

Try disabling the SD SPI interface. That has been known to trash up the SPI interface if not disabled.

void setup()
{
   Serial.begin(9600);

   // sprinkle a little magic pixie dust
   pinMode(4,OUTPUT);
   digitalWrite(4,HIGH);

   // rest of your setup code
}

Posting your code would help.