I figured it out. On all of the virtual directories on the Exchange server, under Directory Security -> Authentication Methods -> Basic Authentication, it has just a "\" under domain. By putting in the NETBIOS name of the domain on all the Enterprise Vault virtual directories, then doing an IISRESET, I was able to get it to work. I actually think I saw something about this in the SP1 release notes, but haven't applied SP1 yet.