Great, this means that /etc/machine.secret is still valid.
If you call univention-ldapsearch without parameters then it uses the server's machine account for authentication against the OpenLDAP directory (bind DN "ucr get ldap/hostdn" and the password from /etc/machine.secret). The reason your "univention-ldapsearch" didn't work is that you told it to search the AD's LDAP directory (the default port, 389, is used by Samba 4's AD LDAP directory, and the OpenLDAP directory is listening on the non-standard port 7389). The naming scheme inside the Samba 4 AD LDAP directory is different from the OpenLDAP one, therefore the machine account's DN used to make the bind doesn't work.
That's quite normal as the server password change script is started regularly via cron. Anyway, the machine.secret is working just fine, and there's no problem with the password change. So let's abandon this line in inquiry.
If you're already reinstalling then there's not much use in debugging this issue further, don't you agree?
Does resolving the server's fully qualified domain name from the workstation work? Meaning does this work: "nslookup bebucsmdc1.your.domain ip.of.your.ucs-master"? If so it may be an issue with the DNS configuration on your workstation (either the domain suffix is wrong or the name server's IP address is).
If your UCS backup DC is working fine and you don't want to re-install the whole domain you can promote the backup DC to a master DC. That's what a backup DC is there for (it's its solve reason for existence, in fact). However, this is a one-way street; you cannot demote it again, and you must decommission your old master DC. See the admin documentation for details.