We solved by doing the following:
On the FOG-Server install Winbind:
sudo apt-get install -y winbind libnss-winbind
Edit the Samba config:
# /etc/samba/smb.conf
[global]
...
workgroup = <domain/workgroup>
...
wins server = <ipofyourwinsserver>
...
Edit the nsswitch config:
# /etc/nsswitch.conf
hosts: files dns wins
Reboot your server.
On the Windows 7 clients we had to add the following firewall rule:
netsh advfirewall firewall add rule name="FOG Service" dir=in action=allow remoteip=<ipofyourFOGserver> protocol=tcp localport=445
That worked for us.