Well comparing the recent voting history of NJ to the amount of swing needed between 2004 and 2008 to flip Indiana and North Carolina, it certainly isn't unreasonable to assume a winning GOP candidate in 2012 could carry NJ.
A Republican hasn't won the presidency nationally with an Obama-style margin since 1988, so it's a bit tough to say for sure which states would be the first to fall. Having a highly-unpopular Democratic incumbent could give us a chance to find out in 2012.
Let's keep in mind here that Obama won 57 percent of the vote in New Jersey, roughly equal to what he finished off with in New Mexico, Minnesota, and Michigan. The Bush campaign poured little to no resources into this state in 2004 and received nearly 47 percent of the vote.
That sounds like a swing state to me.
The state's Democratic vote percentage was artificially boosted in 2000 thanks to Lieberman's presence on the ticket, as well as Gore's overwhelming numbers in the NYC suburbs. Al Gore even won Staten Island in 2000.
Clinton won Staten Island in 1996, and probably deserves the credit for establishing bases of Democratic support there and other suburban areas in the Northeast.
If you notice, since the beginning of the Obama Presidency, many of these suburban areas have been shifting back to Republicans. Without these suburban areas, Pennsylvania would likely be gone for Obama, New Jersey very close, and New York only a 5-7 point win.