It seems to be fixed.
After the move Allen had set the "Full URL to main directory" to use our new server's IP address instead of the domain name. I changed it back, emptied the cache and had the users log out and back in via a link using the domain and they're working happily.
Just hope this works for all of them.