ICS forces a particular IP address for the main server and the clients have to have fixed IPs of a certain range, as well.
Best thing to do is turn off the ICS, get your clients all seeing each other with DCHP/DNS, then hook up NAT. Network Address Translation is pretty well described in the help menus in Windows - it's been around long enough for that.
You didn't mention if the internet connection is a 24/7 broadband connection but if it is, you'll probably want two network cards and a good proxy server.
Hope this starts things in the right direction. I am going off what I remember from the books (a twenty person office has no need for Advanced Server) so take my comments with a grain of salt.
The Netlogon errors probably haveto do with the forced IP address created by ICS not being on the same subnet as your clients. They're looking in the wrong place for information.