Comment 15 for bug 1644098

cat << EOF > /etc/network/if-up.d/zz_restart_dnsmasq
#!/bin/bash
if [[ "\$IFACE" =~ [^tun] ]]; then
  sleep 2
  logger "** Restarting DNSMASQ process because funky network manager crappyness"
  kill \`cat /var/run/NetworkManager/dnsmasq.pid\`
fi
EOF

chmod 755 /etc/network/if-up.d/zz_restart_dnsmasq

Seems to consistently fix the issue for me, nasty hack but meh, works.