I'd still double-check on DNS. I know that it sounds funny, but you'd be surprised at how many wieird things crop up with DNS problems. It only takes a couple of minutes to check too.
First things first. Make sure that your DC is set to the correct DNS server (I'm assuming that it's going to be the localhost here). Also, after starting the DNS console, right click on the server, go to the logging tab (I think it's the logging tab) and run both simple and recursive queries. If they test OK, you should be good to go.
One of your netlogon errors seems to indicate that you rebuilt the domain at some point. Is this correct?