"easy to fix" is relative. This "new domain equals bad" thinking has spread in the IT security world. My corporate anti-virus blocks them too and I see it a lot while browsing HN on the job.

The only real solution, as a "holder of a young domain" is to wait 30 days before you use it.