The environment that this is running in is SCCM 2007 R2 running on a Windows 2008 R2 server. The PXE Distribution point is running on its own Windows 2008 R2 box.
This is what Event viewer showed after trying to start the WDS service:
An error occurred while trying to start the Windows Deployment Services server.
Error Information: 0xC1030104
After this failure, the PXE Service point was removed then the WDS server role was also removed. The PXE point was then added again and the WDS server role was also again added. The service was then restarted but failed with the same error. Based on the information in the following link to tech net, the problem was solved.
These are the step by step directions that were used to solve the issue.
1) Remove the PXE Service Point
I removed the server but this may not be applicable if the SCCM server also serves as the PSP
2) On the PXE server (if it exists) remove the WDS role
4) Add the WDS role but do not set it up, just add it
a. If it fails to start (Error: The description for Event ID 258 from source WDSIMGSRV cannot be
found.) Use the article I attached.
b. Step 4 in the article. Run wdsutil /uninitialize-server will run but it will error out, keep going
on with the next command. It is erroring out because we do not configure WDS, SCCM does.
c. Once you’ve finished the wdsutil /initialize-server verify that the service has started. It did for
me so hopefully that’s all you need to do.
5) Add the PXE Service Point role again within SCCM
6) Wait about 10 minutes for SCCM to update to show that you have a new distribution point for
your boot images
7) In your boot images, re-add the distribution point and make sure it updates.
After these steps were completed, the WDS service started and imaging through SCCM could resume in this enterprise. I hope this helps others fix this problem as I have seen users in many tech forums with the same error code when trying to use PXE and WDS.