Let's take a look:
2008: McCain (AZ) only won Utah, Obama(IL) lost MO and KY
2004: Bush (TX) and Kerry (MA) both won all neighbors
2000: Bush (TX) lost NM, Gore (TN) lost all
1996: Dole (KS) lost MO, Clinton (AK) lost TX and OK
1992: 41 (TX) lost all but OK, Clinton (AK) lost TX and OK
1988: Dukakis (IN) kost all but Illinois
1984: Mondale lost every state except MN
1980: Reagan (CA) won all of them, Carter (GA) lost all of them
1976: Ford (MI) won only IN, Carter (GA won all neighbors
Clinton's not from Alaska