Receiving servers decide the fate of a message from three questions: was this server allowed to send for your domain, was the message altered in transit, and what to do when the first two answers are no.
While the domain lived on the old host, the DNS records answered those questions about the old server. After the move the new server sends and the records still describe the old one — formally, an impostor is sending your mail.
The second factor is reputation. A new server has none yet, so a few days of extra suspicion are unavoidable even with perfect records.