I just fought with something similar, although a bit less complex, and found that KISS (Keep It Simple Stupid) policy was fasted and easiest when dealing with Samba.
The problem with accessing your Network Neighborhood sounds to me to deal with configuring your Windows machines to provide Linux compatible authentication. You have to make/edit an entry in your registry. (Start > Run > regedit)
http://www.tldp.org/HOWTO/SMB-HOWTO-7.html about halfway down the page has the exact instructions for Win9x machines. Yesterday I also configured a WinME exactly the same way and it worked like a charm.
Again, if you can simplify the configuration, such as eliminating the PDC requirement, you have a much better chance at basic communications. I'm small with two windows boxes and another linux workstation, so security/authentication amongst my machines doesn't really concern me. I just want Samba to provide my limited scope (windows) workstations with an access to another world!
Also, have you created a user on your server with exactly the same username/password as your windows machine?