It looks like the rename method needs to specify the "new_superior" attribute with context-specific encoding. From RFC2251 section 4.9 we see:

ModifyDNRequest ::= [APPLICATION 12] SEQUENCE {
        entry           LDAPDN,
        newrdn          RelativeLDAPDN,
        deleteoldrdn    BOOLEAN,
        newSuperior     [0] LDAPDN OPTIONAL }

I've confirmed this fix then matches other LDAP clients, and I can successfully perform an object move in AD. Here's a quick patch which corrects this problem, for your consideration:

--- lib/net/ldap.rb
+++ lib/net/ldap.rb
@@ -1537,7 +1537,7 @@ def rename args
     new_superior = args[:new_superior]
 
     request = [old_dn.to_ber, new_rdn.to_ber, delete_attrs.to_ber]
-    request << new_superior.to_ber unless new_superior == nil
+    request << new_superior.to_ber_contextspecific(0) unless new_superior == nil
 
     pkt = [next_msgid.to_ber, request.to_ber_appsequence(12)].to_ber_sequence
     @conn.write pkt