Hmm, I'd give it a shot with the option "block all traffic until the firewall starts and after the fireweall stops" disabled to see if that helps. I happend to be able to speak with one of our AD admins here, but the machine will need DNS (53) and RPC (445) for sure to be able to join. NetBIOS is a different depending on who you ask.
If it does, I'd maybe have a temporary policy for machines as they are imaged and then move them to a new policy once they're going--assuming your're using a SEPM server.