It sounds like samba may be starting before the network is fully initialized and thus not working until a restart. There may be some interesting information in /var/log/samba/log.smbd.
I would suggest trying to delay the startup of smbd by altering the /etc/init/smbd.conf file; specifically the "start on" line. Suggested alternatives to try are:
...to match the contents of /etc/init/nmbd.conf, or:
start on (local-filesystems and net-device-up IFACE!=lo)
...replace eth0 with the name of your actual network interface, or even:
start on (local-filesystems and net-device-up IFACE=eth0)
...so that it waits until udev completes its magic.
start on (local-filesystems and net-device-up IFACE=eth0 and started udev-finish)