I don't buy at newegg or have any other incentive to side with them but... in my past experiences, Linux didn't really have the most compatible hardware drivers. Am I the only one to think that?
Anyway, the problem here is that Newegg are refusing to replace it simply because of the presence of Linux; by far the most likely explanation is that the hardware really is defective and Linux isn't at fault.