Not necessarily true that teams don't do well at their first Nationals at least from NY. NY teams at their 1st Nationals: CNS (6), Webster (8). No telling.
I think this is definitely true - the two years Mentor has made it out of Ohio, they've placed 5th and 7th respectively, so it's definitely possible. Plus, Solon MS's first year they won (2008) they didn't even make to nats the year before. Anything goes.
What I see as a larger barrier, though, is the fact that NYS has 25 events as opposed to three. Now you might think having fewer events means it'll be easier for Columbia, but it also means there's a small amount of less time these teams can focus on other events.
Furthermore, a lot of states (like Ohio) recently have made their state schedule the nats schedule. This really helps other teams out from those states, and I don't think NY does that. Correct me if I'm wrong though.
Ultimately, like syo and other previous posters have said, I think it will be difficult simply because nats is different. I predict anywhere in the teens for Columbia, because historical placings (see: Bayard Rustin in 2012 and Palo Alto in 2013) show that new teams from strong states do well, but not enough to get top 10.