Please let me know if you find a solution!
I've been playing around with modifications to the USBHost library to make it work better but I simply don't have the time to rewrite it properly! Turning on TRACE_USBHOST in Usb.h makes it work much much better, but at the expense of way too much debug output over serial. I believe it's simply a timing issue: the new Android devices are too slow, or the Due is too fast. Debugging slows down the sketch, thereby giving the Android time to switch to Accessory mode.