It could be that he was just marking it as "his" since it's new (to him, too) or it could be that the previous owner had a cat that sprayed on it! I've heard it's expensive, but alot of people swear by a product called "Feliway" for cats that spray. You might try that if it's within your budget. I think it's sold at pet stores; if not, your vet may have it.