If you put him in a real small room with a litter box, he would learn. Or cage him in a cage big enough for a box. They are pretty smart and learn pretty fast.

You must remember, his life has been turned upsaide down, he is in a strage place and is stressed to the max... Please cut him some slack. If he is use to being outside and now finds himself shut up 24/7 in a house, you can BET, that is adding to his stress and confusion. Cats do not take change very good, it upsets them a LOT! Add to that, he has always went outside to do his business and you got a ready made problem.

Try that small room or cage... He will learn...