How many litter boxes do you have? Do the two cats have to share or does each have at least one of his/her own? Have you tried different litters? There are some that require rather infrequent change.