The chair of the New Jersey Democratic Party has asked the Democratic National Committee to bless the idea that New Jersey should have the first presidential primary. See this story. Democrats hold majorities in both houses of the New Jersey legislature and New Jersey has a Democratic governor, so if the national Democratic Party supports making New Jersey first, then it should be possible for a bill moving the New Jersey presidential primary to February or January to pass. Thanks to PoliticalWire for the link.
New Jersey has been one of the last states to hold presidential primaries. Starting in 1968, the New Jersey presidential primaries have always been in June.
If Presidential primaries were private, then each party could decide its own primary schedule.