I have read through many many pages on setting up this trust and I am still hitting a road block.

I have an existing 2000 domain which all the users, computers, and most of the servers in it.
The company was bought out, and the new server was put in a new 2003 domain for the new company name.

Then I was hired. My plan is to move everything out of the old domain name and into the new one. Work here happens 24/7/365 so downtime is minimum. I want to get a trust setup between the two domains, so I can build a new Group Policy for the company in 2003, refresh all the computers, add them to the new domain, but still have users in the old domain be able to login to them.

During this process I also want to move servers, and user accounts over, but still have them be able to access computers / servers on the old domain.

Anyways.... I setup the trust in AD domains and trusts on the new domain DC, and when i go to confirm the trust, outgoing is fine, but the incoming is not. Basically, no logon servers are available.

I have also tried establishing it from the old domain, and end up where the old domain can not find a logon server for the new domain.

I have tried configuring DNS, WINS, and lost track of everything I did {I was tied up in another project for the last two months}, but I feel like I am missing something very simple.

At a minimum you need to setup DNS forwarding between your two domain's DNS servers. Also you should ensure that NetBIOS over TCP/IP is running since 2000/2003 still makes use of it for trust based communications.