Grimsoul, I built a lovely house right on the outskirts of the beach (upper left hand side of the map shown). They moved in there fine but when I tried to get them to go out for work or opportunities it came up with the route fail stomping of feet etc.
I'm not sure what caused it but I moved the whole house to where one of the bars is located (far right on the map - still on the beach). I still experienced problems (plus I relocated to the empty lot right by the original lot before this).
I ended up removing some of the fencing round my lot which stopped the problem, so I assumed it was the fence as the original problem.
But reading your post has made me wonder if the original problem was the location.... And the fence was a further issue....hmm.