So I actually went out and bought a Samsung CloudPrint ready printer and swapped it out. Worked for about 3 days, then did the exact same thing as the Dell. The issue is either on the Google side, or with the interface on the printer to CloudPrint, as both printers have exactly the same interface for that.
I had to break down and get a Windows computer for my folks so I could just hardwire it in. My conclusion is that Google CloudPrint is just not good enough for prime time.
I did ask for help on the Google side and they were not able to resolve the issue either.