Seems I just had to throw myself at the wall a little longer.
I had been changing the machines name at the same time as joining the domain. When I set the machines name first (and thus rebooted), and then attempted to join the domain it joined just fine.
It has another error waiting for me (of course, that is just the nature of Samba I've learned) but I'll see if I can sort that out myself.
Cheers