In case anyone was following along, I've solved the problem. I'm not sure what technically did it, but I upgraded Samba from 3.0.25a to 3.0.25b. Also, I used the "net" command that came with the package (bin/net) which I apparently wasn't using before (doing a "which net" command). After that I did a kdestroy, kinit, net ads join and all worked again!