The difference is not the mathematical expression, but rather what you are measuring.
Mean squared error measures the expected squared distance between an estimator and the true underlying parameter:
$$\text{MSE}(\hat{\theta}) = E\left[(\hat{\theta} - \theta)^2\right].$$
It is thus a measurement of the quality of an estimator.
The mean squared prediction error measures the expected squared distance between what your predictor predicts for a specific value and what the true value is:
$$\text{MSPE}(L) = E\left[\sum_{i=1}^n\left(g(x_i) - \widehat{g}(x_i)\right)^2\right].$$
It is thus a measurement of the quality of a predictor.
The most important thing to understand is the difference between a predictor and an estimator. An example of an estimator would be taking the average height a sample of people to estimate the average height of a population. An example of a predictor is to average the height of an individual's two parents to guess his specific height. They are thus solving two very different problems.
There seem to be at least two distinct questions intertwined here.
First is the question of the right model for your data. As your response is, and can only be, positive integers it seems unlikely that linear regression by itself is a suitable choice because, as you have found, it may predict impossible values: the choice of figure of merit or error metric is by comparison quite secondary. You have various alternatives open to you, including working with a logarithmic transformation. My top suggestion would be to check out Poisson regression. In R that can be done using glm() and quite possibly in other ways. (R experts may well add much more.) See for an introduction
http://en.wikipedia.org/wiki/Poisson_regression
and for one engaging discussion see
http://blog.stata.com/tag/poisson-regression/
The Stata content of that blog does not render the posting useless or uninteresting to people who don't use Stata.
Poisson regression can only predict positive values. (Those predictions can be fractional, to be understood in exactly the same spirit as statements that the mean number of children per household is 1.2, or whatever.)
The second question is about RMSE and NRMSE. The merit of RMSE is to my mind largely that it is in the same units of measurement as the response variable. Statisticians and non-statisticians should find it relatively easy to think in terms of RMSE of 3.4 metres or 5.6 grammes or 7.8 as a count.
Naturally, nothing stops you scaling it and it then loses that interpretation and becomes a relative measure. It is just what it is and joins a multitude of other such measures, e.g. R-square and its many pseudo-relatives, (log-)likelihood and its many relatives, AIC, BIC and other information criteria, etc., etc. The choice of figure of merit, error metric or of whatever you call them -- if I recall correctly Bowley wrote of "misfit" in 1902; that's a nice word worthy of use -- is partly a matter of personal taste, partly a matter of audience (only technical audiences can be expected to recognise AIC, for example), and mostly a matter of what has become conventional in your field.
Best Answer
I haven't seen RMSLE before, but I'm assuming it's $\sqrt{ \frac{1}{N} \sum_{i=1}^N (\log(x_i) - \log(y_i))^2 }$.
Thus exponentiating it won't give you RMSE, it'll give you
$e^\sqrt{ \frac{1}{N} \sum_{i=1}^N (\log(x_i) - \log(y_i))^2 } \ne \sqrt{\frac{1}{N} \sum_{i=1}^N (x_i - y_i)^2}$.
If we take the log of both sides, we get the RMSLE versus $\frac{1}{2} \log \left( \frac{1}{N} \sum_{i=1}^N (x_i - y_i)^2 \right)$, which is clearly not the same thing.
Unfortunately, there isn't a good easy relationship in general (though someone smarter than me / thinking about it harder than me could probably use Jensen's inequality to figure out some relationship between the two).
It is, of course, the RMSE of the log-transformed variable, for what that's worth. If you want a rough sense of the spread of the distribution, you can instead get a rough sense of the spread of their logarithm, so that a RMSLE of 1.052 means that the "average" is $2.86$ times as big as the true value, or 1/2.86. Of course that's not quite what RMSE means....