Alright, well, it seems I was just rushing things a bit. I left it overnight, came back in the morning and things were semi-working!
Before I went to bed, PXE booting wasn't really doing anything on the client, just that DHCP line with the spinning cursor. When I tried again in the morning it was now contacting the WDS server but halting before continuing on. Looking in the logs I now had this:
WARNING: _SMSTSCertStoreName Not Set. This might cause client failures in native mode. SMSPXE 19/08/2012 12:46:10 p.m. 1740 (0x06CC)
WARNING: _SMSTSCertSelection Not Set. This might cause client failures in native mode. SMSPXE 19/08/2012 12:46:10 p.m. 1740 (0x06CC)
Which indicated it was still a certificate error. In the SCCM console, I went to Administration, Security and then Certificates. In there I had a bunch of blocked certficates and the issued to fields were showing as GUIDs rather than actual FQDNs. To resolve the problem, I opened the properties of each Certificate, noticed that they were showing as not installed so installed them manually to the Local Computer's (the Primary server) trusted store. Once that was done, I unblocked each certificate and then attempted PXE again - and now it's working perfectly!
So the moral of the story I've learn is, if something appears to not be working with SCCM, give it a few hours and see if it clears itself up...