Gareth, I agree with Clinton that a good start is to avoid the other side of the street when you walk your dog, particularly on or near the new neighbor's property. If the cat is going off-property to go after your dog, you could try some harmless deterrents such as squirting water at the cat with a water pistol, or shaking an aluminum can with some stones in it (or using some other noisemaker... maybe not a banjo, though; walking a dog while playing it is difficult!).

You may also wish to consult the neighbors themselves; if they're cooperative and if you ask nicely, they may divulge an effective solution that has worked for their previous neighbors!