Samba 3.5 documentation states:

With both MIT and Heimdal Kerberos, it is unnecessary to configure the /etc/krb5.conf, and it may be detrimental.

And further:

MIT's, as well as Heimdal's, recent KRB5 libraries default to checking for SRV records, so they will automatically find the KDCs. In addition, krb5.conf only allows specifying a single KDC, even there if there may be more than one. Using the DNS lookup allows the KRB5 libraries to use whichever KDCs are available.

And it says it will look up the _kerberos records in AD to get the information on the REALM:
host -t SRV _kerberos._tcp.MYDOMAIN.LOCAL
_kerberos._tcp.MYDOMAIN.LOCAL has SRV record 0 100 88 myads1.mydomain.local.
_kerberos._tcp.MYDOMAIN.LOCAL has SRV record 0 100 88 myads2.mydomain.local.

So why can't my kinit client find the KDC?:

kinit [email protected]
kinit: Cannot find KDC for requested realm while getting initial credentials

In the end I did it manually by editing /etc/krb5.conf to include my REALM details:

[logging]
 default = FILE:/var/log/krb5libs.log
 kdc = FILE:/var/log/krb5kdc.log
 admin_server = FILE:/var/log/kadmind.log

[libdefaults]
 default_realm = MYDOMAIN.LOCAL
 dns_lookup_realm = false
 dns_lookup_kdc = false
 ticket_lifetime = 24h
 renew_lifetime = 7d
 forwardable = true

[realms]
 MYDOMAIN.LOCAL = {
  kdc = myads1.mydomain.local
  admin_server = myads1.mydomain.local
 }

[domain_realm]
 .mydomain.local = MYDOMAIN.LOCAL
 mydomain.local = MYDOMAIN.LOCAL

To Join the Domain in the OU I wanted I performed the following command

/etc/nsswitch.conf
passwd:     files winbind

shadow:     files

group:      files winbind
Darn seLinux:

setsebool -P samba_enable_home_dirs 1