The sentence "Wishes for the new year" can be translated as
"Neues Jahres Wunsche"
or something with a similar form?
How about "Gutes Neues Jahr" or simply "Gutes Neues"? When it comes to it, this is effectively what people actually say and I think it conveys the equivalent meaning.
If you say 'Wünsche für das neue Jahr', shouldn't für make it dative and imply das -> dem and neue -> neuen?
Actually, never mind. I realized für is an accusative preposition.
zum neuen Jahr is surely a valid alternative?