10ppm is 26sec/month. The cheapest 16MHz crystal on digikey is 50ppm tolerance, so at worst with no calibration will be just over two minutes per month. If you do a small amount of calibration (add/sub milliseconds per day at midnight), and the temperature is just normal temp that a room would be, then the performance can be very respectable.
It sounds like your ethernet code may well have been completely hogging the processor (maybe disabling interrupts as part of it?). It's not hard to just make sure that processor can always service something like a 1 ms interrupt off a hardware counter.
Sure you can put a DS1307, then calibrate the crystal on that, but unless you must have battery backup, the IC is more expensive than an ATmega328p.