I was in a similar situation and was between the Nikon P510 and the D3100. I opted for the P510.
I spoke to the guy in the shop who told me the D3100 may give me fractionally better pics in some scenarios due to the extra controls. However, in 'normal' scenarios the P510 would give me excellent quality pics and to get a 42x zoom on the D3100 would cost a small fortune.
Therefore, wanting to take pictures of landscapes, mountains and nature, I opted for the P510 to get the extra zoom capability. I can;t comment on it yet as it was only bought a couple of days ago and not really used yet.