Alright after a long week and a half of pullling my hair out and opening an incident with Novell we have a fix for the issue.
We found we were having DS issues on the server. I had the issue backwards. What was happening was every 45-60 minutes NDS was locking up on the server. Cause and effect being that DHCPD needed to talk back to NDS to get information. Since NDS was locking up this is what was causing users not to get an IP when they booted up. The short version of the fix is that the DS Agent Cache Configuration size was set too low. By default it was set to 64MBs. The dib size was 58 MBs. hence DS would try to do a sync etc and it would lock the cache up and nds would hang. To resolve this log into NDS iMonitor.
https://(servername/ip):8030/nds
Click on Agent Configuration then on Database Cache
Change the Cache Maximum Size to 6x the dib size and make sure the Make Permanent is checked.
This fixed the issue with DS locking up.