I don't have much to add to what has already been said, but to reiterate:
¤ Never leave clothes on the floor, that is an invitation to be peed on
¤ One stressor at a time - he just moved to your home, changing his diet is stress on top of stress
¤ Getting a second litter box would have been my first suggestion, as well as cleaning the diarrhea as soon as he goes. Wash the pan as well if it gets soiled. Cat Attract is a great idea.
¤ Washing linens, clothes, and curtains, as well as the floor with a good enzyme cleaner such as Anti-Icky-Poo or Unique Distributors is a must. The stuff at the local pet store just won't cut it.
¤ Past testing is just that - in the past. Your vet can do a fecal at the office, but if he doesn't see anything and the diarrhea isn't resolving I would strongly recommend you send out a diarrhea PCR panel. It's expensive, but if there is something there that has flared because of the stress of the new home and diet change you need to know so that you can treat it appropriately.