I don't know if there's really much you can do to stop them. It has to do with the trauma of relocation, which you're probably familiar with. In case you're not, cats are extremely territorial and given to complete freak outs when they're taken out of their environments and put into a new one (I have cat stories from my experiences moving - many of them, in fact). If you moved them into a home where the most recent tenant had cats, then yours are not only freaked out over the new environment, but they're also trying to mask the old cats' smell (which may be too faint for you to smell).
The last time I moved cats, I made sure to bring a number of their toys, a scratching post that still had some of their hair on it, and put fresh litter in their box without otherwise cleaning it. I placed all of these in one room, before moving any furniture into the apartment, brought them into the room in their carriers, and just opened the carrier doors and allowed them to come out on their own. When they finally did, they went straight to the familiar objects and seemed almost calm. It just took a little time to break them in to the rest of the place.
Good luck - sorry to hear about your domestic troubles.