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.