johnwasser:
Sounds like the replacement ATmega328P chip has the Duemilanove bootloader instead of the UNO bootloader (optiboot). That should not cause a problem with the ethernet shield.
Hmm I have multiple chips... Would it make a difference if I try to (re)burn the correct bootloader?