(resent because I forgot to CC qubes-users)
You could try to create a new net-vm, assign your network hardware and start this instead. Maybe it's some incompatability with the config files. If it works, set it as standard net-vm.
Another thing you could try is: before shutting down your net-vm, right-click on the NetworkManager applet and untick "Enable Networking". I have to do this when I'm in one specific wlan, because otherwise after a restart of the net-vm I won't get an ip assigned (no clue why but this reliable solves the issue for me).
slideshowbob