My cat used the litter box fine until we got a second cat. The second cat is wonderful but has the stinkiest poo I've ever smelled and the first cat refuses to use the same little box. We put a second litter box in my daughter's room, where the first cat practically lives, and that helps during the day, but the cat is too active at night so we put her downstairs, where she poops on the floor. The first cat is smaller, so I thought I could get another box for her - but how do I keep the second cat from using her's?
Good job in getting another litter box. Some people who just think that the cats will just have to work it out and go in the same box, so well done.
Is there another litter box downstairs that your first cat can use? Sometimes you may have to have a little box in a few rooms, as it gives the cat the choice of where they want to go. Make sure it is in an area that feels secure to your cat (not in the middle of the room but maybe hidden behind a door). A bit more privacy.
Cats generally have smellier urine and poo than dogs as their diet has a higher meat content in dry and wet food (cats are carnivores that need a chemical called taurine to keep their eyes healthy). What this does is to make their liver produce more creatinine, which is a waste product that every mammal produces in their urine and poo. It may be a good idea to take your second cat for a urinalysis and fecal float test at the vet to check their liver enzymes.
Good luck with your cats and their bowel movements :)