Are the boot.wim files under c:\program files\landesk\pxe\system\images\boot on the PXE rep's the same version?
I assume you are using WinPE here, so what happens if you use the command prompt on the machine in WinPE to check the network settings that it has been assigned?
I know the network guys have said 'nothing has changed' but very often that equates to 'nothing has changed that we consider is relevant to you'.
Do an ipconfig on a box on that network and verify the settings and do some tests for names other than the core server. Perhaps the dhcp server for that subnet isn't providing the correct domain suffix or something like that.
LANDesk Silver ESP
The One-Stop Shop for LANDesk Enhancements
Boot.wim was corrupted on the core. LD support fixed the issue.