When dealing with litterbox problems:
- Make sure it isn't a medical issue, by taking the cat to the vet. In this particular case, since there was a really obvious change, this is likely not the problem, but it doesn't hurt to make sure.
- Make sure there isn't something the cat doesn't like about the litterbox, or if there is something that is stressing out the cat.
In the general case, it usually helps if you can think of some change that may have caused the cat to stop using the box. Like a change in the box or the room where the box is located, or a change in the cat's routine, and so forth. In your particular case of course, the change is obvious, which is that you just moved, and the cat's entire environment has been disrupted. But because the cat has never used a box before, it may also be the case that there is something about the box that it finds less than appealing, and you simply don't know it's preferences. Some different things to consider:
- The box's location. It may be in a place that's too busy for the cat, or in a room it normally avoids.
- The type of box. A simple pan type box with low sides is usually the most appealing type for a cat. If the box has a lid, or high sides, or is top entry, and so forth, all those make it that much less easily accessible. Self cleaning boxes may also deter cats.
- The type of litter. Texture is the main issue. Some types may be unpleasant to walk on, and others may seem more like obvious digging material to the cat. Some types may help reduce smell, which might help, as cats don't like smelly boxes either.
- Size of the box. Bigger is always better. If the box is too plain small for the cat, it may not use it.
- Litter depth. Neither too shallow nor too deep. About three inches is optimal.
- Cleanliness. The box should be cleaned at least once a day.
- Smell. Make sure to use pet odor removing cleaning products around any places the cat had used that it shouldn't. There are also cat attractant sprays that might help attract your cat to the box.
Litterbox problems can also crop up after moving, as the cat is not used to the new territory. So it's generally a good idea when you move to introduce your cat to the new house one room at a time, so you can be absolutely sure the cat knows where its box and things are.
Therefore, I think it's likely you will need to retrain your cat by reintroducing it to your new house. Start out by keeping your cat in a very small room, like a bathroom. The room should of course have everything the cat needs, but also be small enough that it doesn't have many options than to use the box. Cats don't like to eliminate in areas they use for other things, like eating or drinking, so a small room will help encourage proper habits. Make sure while doing this process to spend time with your cat in its room as well, so it's not getting too bored and lonely.
Once the cat had been eliminating in the box for a while, about a week, then you can re-introduce your cat very slowly to the rest of the house. Give it an additional room to explore, but only let it out while supervised. If you happen to see it about to eliminate, distract the cat by clapping your hands at it, throwing a toy by it, etc., and then take it back to its box. Put it back in its room when you cannot supervise it. Once you are satisfied with the one additional room, give it another, and so forth.
Continue this process, and over time, as you feel more confident, you can supervise it less and less.
Once you are satisfied the cat is now trained, you can do things like attempt to, very gradually, move its box to a new location, or let it outside, and so forth.