There are two readings similar to what you described, but you've over-negated in your paraphrases:
1. This is the first year they didn't celebrate New Years.
2. The first New Years wasn't celebrated by them.

I'm not sure that the ambiguity is really about scope of the negation at all. Instead, it may just be about where the "for the first time" adverbial attaches structurally (within the verb phrase or to the clause as a whole). There might be additional readings possible if we also include scope of the negation, although they might be logically equivalent to those two readings generated by the adverbial attachment.

Note: for my ears, it must be "New Years" (e.g., a holiday, for some reason written in a plural or perhaps possessive form), unless you use it as a normal noun phrase with a determiner: "the new year".

My default interpretation would be low attachment, meaning "the first new year", or reading (2). But that is pragmatically bizarre (which is the "first" new year??), so unless the context permitted that, I would probably reinterpret it to fit as this being the first time they didn't, meaning they always have before. In other words, this is a very flexible ambiguity that is interpreted in context, without a strong bias one way or the other. It's a confusing example and could be clarified with a more controlled situation (rather than something that happens so rarely and repeatedly without a beginning).