Correct, we've seen countless times in the past where new/moved/? domains struggle with the internal filters over there at Gmail. You can pass SPF/DKIM/DMARC/etc and most of the time you're going to land in the Inbox - but every once in a while - their filters take issue with a domain and additional steps are necessary to resolve it. We've corrected this for customers in the past with the method Zach noted by sending messages to test Gmail accounts and then clicking the Not Spam/Not Junk option on those messages. After a few of those you should stop seeing their filter force your messages into junk mail.
Kyle Kerst
Lead Internal Network/System Administrator
SmarterTools Inc.
smartertools.com