How can the MSE of predictions be greater than the variance of the response variable? I saw an example on a blog where a k nearest neighbors algorithm was run to predict responses on a test data set.The MSE(mean squared error) of the predictions was larger than the variance of the response variable in the test set. Shouldn't the MSE always be less than the variance of the response variable as SSTO(total sum of squares) = RSS(model sum of squares) + SSE(error sum of squares).

 A: Case 1:
SST (total) = RSS (model) + SSE (error)
This is only true in general if the model includes an intercept (and, in relation to case 3, if the mean of the errors is 0).
(more precisely, you do not need an explicit intercept, for instance for linear regression it is sufficient that the intercept is in the column space of the regressors)
See for instance the following y=bx fit:

Clearly the error is much larger than the total variance in the data.

Case 2:
Other issues may be when you are comparing training vs test, but it is unclear whether this is the case in this question. (there is an explicit 'in the test set' mentioned, but is this the same for all terms?)
(see for instance https://stats.stackexchange.com/a/299523/164061 and the four other links in that post)
Case 3:
In the test set a similar effect may occur as with the lack of the intercept. If the model (which you fitted to the training set, and not to the test set) is not a good fit for the test set, then you may get a larger error than the total variance. (this is what Firebug meant with, 'makes sense to the training data only)
This bad fitting, for which the SSE becomes larger than the SST, is especially likely when you are over-fitting.
Case 4:
If you are fitting a Bayesian model, or some model that has bias (e.g. regularisation) then there is no guarantee that SST (total) > RSS (model).
A: The MSE is defined as $MSE = N^{-1} \sum_{i=1}^N (y_i - \hat{y}_i)^2$, where $\hat{y}_i$ is the fitted, or predicted, value. 
The variance is $V = N^{-1} \sum_{i=1}^N (y_i - \bar{y})^2$, where $
\bar{y} = \sum_{i=1}^N y_i$. 
It is true that in most cases, MSE will tend to be smaller than $V$, but it depends inherently on how the model fits the values $\hat{y}_i$ to the data. Given that there is some noise and some signal in the data, it will often be the case that the MSE is smaller, but not always. 
