Initially I managed to get machines to bind by manually creating an edu.mit.Kerberos file and populating it before performing the actual bind. This would work but a reboot would often cause a 'Network Accounts Unavailable' message.
The opendirectoryd logs were full of messages such as 'No preferred destination' and 'Failed to retrieve keychain password for 'MACHINENAME$' module '' node '/Active Directory/DOMAIN'.'
On a whim I tried disabling IPv6 on the ethernet adapter -- which is apparently no longer possible using the GUI in 10.7. Once I disabled it from the command line the machine bound without the need to create a kerberos file and authentication worked perfectly.
You can disable IPv6 from the command line with:
networksetup -setv6off Ethernet
Alternatively the script below will disable it on all adapters:
#!/bin/sh
services=$(networksetup -listallnetworkservices | grep -v "*");
for service in "${services}"
do
echo "Disabling IPV6 on ${service}";
networksetup -setv6off "${service}";
done
exit 0
[crarko adds: I haven't tested this one. Looking at the man page for the networksetup command gives -setv6automatic or -setv6manual as the parameters to enter to re-enable IPv6 using the above command.]

